Problem: To find the nth position element in an Inorder traversal of a Binary tree. Each node in the Binary tree contains the size of the tree underneath.
Examples:
For a tree with root:node1, left child: node2, right child: node3
Input: 1, Output: node2
Input: 3, Output: node3
Algorithm:
1.Traverse the tree to find the node where required inorder position is equal to weight of a node
2.Weight of each node is determined by keeping track of the size of the tree traversed.
3.If node’s weight is less than inorder position then go left else go right and carry the weight of the current node
Java Code:
