Interview Q: Binary tree Inorder traversal

Question

I was asked this question in an interview.

Problem: A binary tree and the height of corresponding sub-tree is also given to us. Then we have to find an element at particular position in inorder way.

For example: Tree structure is : D (Root Node)[subtree-size = 6] --> B,F(Child Nodes of D)[subtree-size = 2] --> A,C,E,G(leaf nodes)[subtree-size = 0].

So there are total 3 levels: Level 0: D; Level 1: B,F; Level 2: A,C,E,G

We have to calculate Node at particular order/position in inorder, say p. if p=2 then node would be B (inorder traversal).

My Solution: I have suggested that we need to do inorder traversal once(through BFS/DFS) and then we can give the i-th order node and time complexity would be O(n).

Now I was asked that can I improve the solution based on sub-tree size information. But I can not come up with any way where sub-tree size can decrease the time complexity.

Can sub-tree size information reduce the time complexity? If yes then please share algorithm/pseudo code.

Answer 1

If we want to find the element at the i-th position in the inorder traversal:

• We know we're looking for the root if the left subtree has exactly i-1 nodes.
• We know it will be in the left subtree if the left subtree has i or more nodes.
• We know it will be in the right subtree if the left subtree has less than i-1 nodes.
• We can repeat this recursively by updating i appropriately. More specifically, we need to decrease i by the size of the left subtree plus one whenever we go to the right subtree, as the inorder traversal of that subtree will start at that position of the original inorder traversal. We don't need to change i when going to the left subtree, as the inorder traversal of that subtree will start at the starting position of the original inorder traversal.

So, in pseudo-code, we can do the following:

currentNode = root
while true
  if getSubtreeCount(currentNode.left) == i-1
    return currentNode
  else if getSubtreeCount(currentNode.left) < i-1
    currentNode = currentNode.left
  else
    currentNode = currentNode.right
    i -= getSubtreeCount(currentNode.left) + 1

This will give us a running time of O(treeHeight).

Example:

Say we have a tree:

     D
   /   \
  B     F
 / \   / \
A   C E   G

Say we're looking for the 2nd position in the inorder traversal. We'd start off with D. We'd see that the left subtree has 3 nodes, so we know the 2nd position is in the left subtree. Looking at B, we see the left subtree has 1 node, so we know B is in the 2nd position.

Say we're looking for the 5th position in the inorder traversal. We'd start off with D. We'd see that the left subtree has 3 nodes, so we know the 6th position is in the right subtree. Looking at F, we now look for the 1st position since there's 4 nodes in the inorder traversal before we get to the subtree with F as the root. We see the left subtree has 1 node, so we know that subtree contains the node in the first position. Looking at E, we see the left subtree has 0 nodes, so we know E is in the 1st position in this subtree, i.e. the node we're looking for.