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,

Input:

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

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++ –

Output:

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

(2 votes, average: 5.00 out of 5)