122 – Trees on the level

Given a binary tree, write a program that prints a level-order traversal of the tree. In a level-order traversal of a tree, the data in all nodes at a given level are printed in left-to-right order and all nodes at level k are printed before all nodes at level k+1.

For each completely specified binary tree in the input file, the level order traversal of that tree should be printed. If a tree is not completely specified, i.e., some node in the tree is NOT given a value or a node is given a value more than once, then the string “not complete” should be printed.

The input is a set of (n, s) pairs, where n is the value at a node and s is a string that specifies the path to that node starting from the root. For example, (10, RL) is the node at root –> right –> left, and has a value 10. The root has a blank string for its path — (5, ). [Source]

Category: graph theory, data structures, BFS

Discussion: There are several ways to approach this. The way I approached it is to assign a numeric position to each node based on its position in the tree and then doing a BFS starting from the root.

Assigning positional values is similar to the array representation of a binary heap. If a node has a position k, then its left child takes the value 2k + 1 and right child 2k + 2. The root takes a positional value of 0, ‘L’ takes 1, ‘R’ takes 2. The positional value can be computed using a the following recurrence.

P(root) = 0
P(path) = 2 * P(path – last_node_in_path) + 1, if last_node_in_path = ‘L’
P(path) = 2 * P(path – last_node_in_path) + 2, if last_node_in_path = ‘R’

Store the node (position, value) in a hash-table. Once this is done, do a BFS starting from the root (i.e. node with position 0), adding nodes at positions 2k + 1 and 2k + 2, if they exist, to the BFS queue. Eventually, when the queue is empty, you have a level-ordered traversal if you have as many nodes as were input. Else, the tree is disconnected and hence “not complete”.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: