Finding nth inorder node of a binary tree where each node contains number of left nodes in its subtree

Question

I came across this problem and can't seem to find a solution for it anywhere.

Given a binary tree where each node contains a number denoting the amount of left nodes in its subtree, write a function that returns the nth inorder traversal node.

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.leftNodes = 0

Finding the nth node of inorder traversal is fairly trivial, but how can I use the information about number of left nodes to improve the process?

Answer 1

As @m69 gave the hint - you can use the left-node count to avoid some un-necessary steps.

Assume having tree where the root have 10 nodes in his left sub-tree: then when asking for node n-th (when in-order) then if n= 1-10 then the answer will be in the left sub-tree. However if n= 11 then answer will be the root, else the answer will be in the right sub-tree.

Consider the following pseudo code:

findNnode(TreeNode root, int n) {
    if (root.leftNodes + 1 == n )
        return root; 
    if (root.leftNodes <= n)
        return findNnode(root.left, n)
    newN = n - root.leftNodes - 1; // after substract all node who came before in in-order
    return findNnode(root.right, newN)
}  

Hope that helps!