Finding border of a binary tree

Question

We are given a binary search tree; we need to find out its border.

So, if the binary tree is

           10
       /         \
     50           150
    /  \         /   \
  25    75     200    20
 / \           /      / \
15 35        120    155 250 

It should print out 50 25 15 35 120 155 250 20 150 10.

If the binary tree is

               10
           /         \
         50           150
        /  \         /   
      25    75     200   
     / \   / \    
    15 35 65 30  

It should be like 50 25 15 35 65 30 200 150 10.

How can this be done? Does generalising this for a binary tree make the problem any harder?

Any help through links will also be appreciated.

P.S.: please see that the pattern does not start from root but from the left (in this case). It might also start with right, but it always ends with the root.

Answer 1

What you are asking for is a modified depth-first traversal where the node's values are only printed/returned if either 1) the node is a leaf node or 2) the node is along the "outer path" of the tree, where "outer path" is defined as

A node is a part of the "outer path" if you arrived at the node by following all of the left (or right) paths from the root, or if the node is the right (or left) child of a parent node that was itself a part of the "outer path" but had no left (or right) children.

If you know how to code DFS, then the modification here could be implemented by checking a few extra conditions during the traversal.

Answer 2

I'm not sure if it matters whether this a binary tree or not. I think the walk algorithm would be the same either way.

Start with the left subtree, and do a modified breadth first walk that prints a node only if it's the left sibling or an edge. this will print the left siblings until it hits the edges, then print the leaves out.

Then you do a modified depth first walk on the right tree that prints either the right sibling or a leaf. This will print all the right subtree leaves, and then the right siblings.

Answer 3

Please ignore this post. This approach will not work.

This can be done in three stages :-

1) In first stage we will travel only to the left till we hit a node which do not have any left node. Print all the nodes traveled.

2) In second stage print all the leaf nodes. This could be normal inorder traversal, where we are only printing the nodes which do not have any children.

3) The third stage is mirror image of stage 1, where we will be traveling only the right nodes till we hit the node which do not have right node. Once this sequence found we can print this in reverse.

The only thing is some glitches at the corner where it may possible that a node can be displayed twice. But this can easily be avoided by checking the last node of each stage with first node of next stage.