Building tree from preorder traversal - PrismoSkills
Given a preorder traversal, there can be lots of binary trees.
But if try to keep the tree nearly balanced, then there is only one solution for a given traversal.
O(n) solution:
If we use the trick from BST test, then there is no need to find the element 'k'
Every next data in the input is checked to see if it lies within the range of parent-node.
If the data falls within the range, then it forms the left/right child of current node, else it is compared with parent of parent.
Read full article from Building tree from preorder traversal - PrismoSkills
Given a preorder traversal, there can be lots of binary trees.
But if try to keep the tree nearly balanced, then there is only one solution for a given traversal.
O(n) solution:
If we use the trick from BST test, then there is no need to find the element 'k'
Every next data in the input is checked to see if it lies within the range of parent-node.
If the data falls within the range, then it forms the left/right child of current node, else it is compared with parent of parent.
Read full article from Building tree from preorder traversal - PrismoSkills
