Traversing A Tree
Problem:
Given a Binary Tree. You have to print the data in inorder traversal.
Restrictions: No recursion, no queue, no stack, no extra memory...
Suggested Solution:
One could use a single additional integer N to hold the path to nodes in the input tree - the number's binary equivalent will signify a path from root to some element: the first bit in the binary string stands of root; then for each successive bit, if bit is 0, move to the left child of the current element and if the bit is 1 move to the right child. For instance the value of N=9 with binary string 1001 signifies the path to the node reached from root (the first 1 in the binary) by a left-left-right (0-0-1)path from root. The mapping from the value of this number N and elements in the input tree is one-one.
For in-order traversal, one could find the next element at each step as follows. We maintain throughout a single integer whose binary representation gives the path from root to the current element in the traversal. This binary string keeps getting bits added or removed from it as we progress. Appending a 1 to the binary string implies multiplying the integer by 2 and adding 1; deleting a 0 at the end, corresponds to dividing the integer by 2 and so on.
The traversal begins at the left most element of the input tree (need not be a leaf) - got by starting with a binary string with a single 1 and adding as many 0's to it as allowed by the input tree.
Cases:
1: If you are currently at a leaf at the end of a leftward going branch, the next element in traversal is its parent. this parent is reached by dropping a 0 from the end of the binary string (path) to the current element.
2. If you are at a leaf at the end of a right going branch, the next inorder element is got by backtracking up to its nearest ancestor A which is the left child of some other node, say P and return P. This can be done by dropping 1's from the end of the binary string corresponding to current element till a 0 is reached and then dropping one 0.
3. If you are at any other element, the next element in the traversal is the left most leaf element of the right subtree starting at the current element. This next element can be reached by the following process:
If possible append a 1 to the binary string. Append as many 0's as possible - if corresponding nodes exist in the input tree. Wherever no more 0 can be appended, stop and return that element. If no 1 can be appended at the beginning, the current element, though not a leaf ought to be treated as a leaf. If the present last bit of the binary number is 1, execute case 2. if the last bit is 0, execute case 1.
The traversal ends when one finds oneself at the root on dropping a 1 from the binary string.
Thus we seem to have carried out the in-order traversal using only a single extra integer.
Given a Binary Tree. You have to print the data in inorder traversal.
Restrictions: No recursion, no queue, no stack, no extra memory...
Suggested Solution:
One could use a single additional integer N to hold the path to nodes in the input tree - the number's binary equivalent will signify a path from root to some element: the first bit in the binary string stands of root; then for each successive bit, if bit is 0, move to the left child of the current element and if the bit is 1 move to the right child. For instance the value of N=9 with binary string 1001 signifies the path to the node reached from root (the first 1 in the binary) by a left-left-right (0-0-1)path from root. The mapping from the value of this number N and elements in the input tree is one-one.
For in-order traversal, one could find the next element at each step as follows. We maintain throughout a single integer whose binary representation gives the path from root to the current element in the traversal. This binary string keeps getting bits added or removed from it as we progress. Appending a 1 to the binary string implies multiplying the integer by 2 and adding 1; deleting a 0 at the end, corresponds to dividing the integer by 2 and so on.
The traversal begins at the left most element of the input tree (need not be a leaf) - got by starting with a binary string with a single 1 and adding as many 0's to it as allowed by the input tree.
Cases:
1: If you are currently at a leaf at the end of a leftward going branch, the next element in traversal is its parent. this parent is reached by dropping a 0 from the end of the binary string (path) to the current element.
2. If you are at a leaf at the end of a right going branch, the next inorder element is got by backtracking up to its nearest ancestor A which is the left child of some other node, say P and return P. This can be done by dropping 1's from the end of the binary string corresponding to current element till a 0 is reached and then dropping one 0.
3. If you are at any other element, the next element in the traversal is the left most leaf element of the right subtree starting at the current element. This next element can be reached by the following process:
If possible append a 1 to the binary string. Append as many 0's as possible - if corresponding nodes exist in the input tree. Wherever no more 0 can be appended, stop and return that element. If no 1 can be appended at the beginning, the current element, though not a leaf ought to be treated as a leaf. If the present last bit of the binary number is 1, execute case 2. if the last bit is 0, execute case 1.
The traversal ends when one finds oneself at the root on dropping a 1 from the binary string.
Thus we seem to have carried out the in-order traversal using only a single extra integer.
posted by R.Nandakumar @ 3:16 AM
0 comments
