Problem Detail: Given a path down a full binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing “go left” and $1$ representing “go right”), how would one find the position of the node in the preorder traversal. In other words the $i$th node in the preorder traversal will end up with at this node. Obviously something better than brute force would be nice.
Asked By : Realz Slaw
Answered By : Realz Slaw
Essentially the algorithm is:
- Each time you go left, you add one.
- Each time you go right, you add the size of the left sub-tree, and you add one.
The size of a full binary tree can be calculated as $2^{h+1}-1$. Thus, the height of the left sub-tree can be calculated by $2^{h_{text {subtree}}+1}-1=2^{h-l+1}-1$ where $l$ is the level of the left sub-tree.
#WARNING: non tested, python-ish def calc_tree_size(tree_height): return (1<<(tree_height+1)) - 1 def inorder_traversal_position(tree_height,path): result = 0 for level in range(len(path)): if path[level] == 0: #If we go left, #Preorder goes left after visiting a node. #Add one for the node we just visited. result += 1 elif path[level] == 1: #If we go right, #Preorder normally goes left, visiting all the nodes # in the left sub-tree before going right. #Add the number of nodes in the left sub-tree. left_subtree_level = level + 1 left_subtree_height = tree_height - left_subtree_level left_subtree_size = calc_tree_size(left_subtree_height) result += left_subtree_size #Add one for the node we just visited. result += 1 return result
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/7346
