Sandy Sandy - 5 months ago 12
Java Question

Left or Right View of an Tree

What is the efficient code to provide the left/right view of an tree.

EX:-

1
/ \
left view--->> 4 7 <<--right view
/ \ /
3 2 9
/
8


The Left view for this Tree is- 1 4 3 8 and the right view is - 1 7 9 8

I have tried with level order traversal, But if the tree have some missing child's then it is difficult for me to find the starting point(in case of left view) or end point (in casse of right view) for the level, Please give suggestions

Answer

You're right that, with a level-order traversal like

Queue<Node> queue = new ArrayDeque<Node>();
for (Node node = root; node != null; node = queue.poll()) {
    if (node.leftChild != null) queue.add(node.leftChild);
    if (node.rightChild != null) queue.add(node.rightChild);
}

it's difficult to know where one level ends and the next begins. This can be addressed by using two queues.

Queue<Node> currentLevel = new ArrayDeque<Node>();
if (root != null) currentLevel.add(root);
while (true) {
    Node node = currentLevel.poll();
    if (node == null) break;
    /* node is the leftmost on its level */
    Queue<Node> nextLevel = new ArrayDeque<Node>();
    do {
        if (node.leftChild != null) nextLevel.add(node.leftChild);
        if (node.rightChild != null) nextLevel.add(node.rightChild);
        node = currentLevel.poll();
    } while (node != null);
    currentLevel = nextLevel;
}
Comments