Construct a full binary tree from preorder sequence with leaf node information

Write an efficient algorithm to construct a full binary tree from a sequence of keys representing preorder traversal, and a boolean array which determines if the corresponding key in the preorder traversal is a leaf node or an internal node. A full binary tree is a tree in which every node has either 0 or 2 children.


For example,


Preorder traversal : { 1, 2, 4, 5, 3, 6, 8, 9, 7 }
Boolean array      : { 0, 0, 1, 1, 0, 0, 1, 1, 1 }

(1 represents a leaf node, and 0 represents an internal node)

Output: Below full binary tree

Full Binary Tree

The idea is to first construct the root node of the full binary tree using first key in the preorder sequence. Then using given boolean array, we find if the root node is an internal node or a leaf node. If root node is an internal node, we recursively construct its left and right subtrees.

To construct the complete full binary tree, recursively repeat the above steps with subsequent keys in the preorder sequence. This is demonstrated below in C++ –


Download   Run Code


Preorder Traversal of the constructed tree is:
1 2 4 5 3 6 8 9 7

1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of