Python Program to Find Nth Node of Inorder Traversal

In the following example of a Python program that finds the nth node of the inorder traversal of a binary search tree :

Program :

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)

    def nth_node_inorder(self, n):
        if self.root is None:
            return None
        count = [0]
        return self._nth_node_inorder(self.root, n, count)

    def _nth_node_inorder(self, node, n, count):
        if node is None:
            return None
        left = self._nth_node_inorder(node.left, n, count)
        if left is not None:
            return left
        count[0] += 1
        if count[0] == n:
            return node
        right = self._nth_node_inorder(node.right, n, count)
        if right is not None:
            return right
        return None

# Example usage
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(1)
tree.insert(4)
tree.insert(6)
tree.insert(8)

n = 4
nth_node = tree.nth_node_inorder(n)
if nth_node is not None:
    print("The", n, "th node of the inorder traversal is:", nth_node.value)
else:
    print("The tree has fewer than", n, "nodes.")

Output :

The 4 th node of the inorder traversal is: 5

In the above example, the `Node` class and `BinaryTree` class are the same as in the previous examples. The new method `nth_node_inorder(n)` finds the nth node of the inorder traversal of the binary search tree, where `n` is a positive integer. It initializes a counter `count` to zero and calls the helper method `_nth_node_inorder(node, n, count)`, which performs a recursive inorder traversal of the binary search tree.

At each node, the counter is incremented and checked against `n`. If the counter is equal to `n`, the node is returned as the nth node of the inorder traversal. Otherwise, the method continues the traversal.

The example usage at the bottom of the program constructs a binary search tree with some example values, and then calls `nth_node_inorder(n)` to find the nth node of the inorder traversal of the tree.

The value of `n` is set to 4 in this example. If the nth node exists, its value is printed, otherwise a message is printed indicating that the tree has fewer than `n` nodes.