Finding border of a binary tree

We are given a binary search tree; we need to fin开发者_开发问答d 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.

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.

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.

printBorder(node *n){

   printLeft(n);   O(log n)
   printBottom(n); O(n)
   printRight(n);  O(log n)
}

printBottom(node *n)
{
  int h = treeHeight(n);
  printBottomHelper(n, 0);
}
printBottomHelper(n, h, max)
{
   if(h == max) {
    print n->data
  }
   printBottomHelper(n->left, h+1, max);
   printBottomHelper(n->right, h+1, max);
}
printLeft(node *n)
{
  while(n!= null){
   node *l = n->left;
   l!= null ? print l->data:1
   n =l;
  }
}

You can maintain two booleans to say what to print.

Call printBorder(root, true, true) to begin. Edit : Doesn't print root at the end, but at beginning, should special case that.

function printBorder(
Node node, bool printLeft, bool printRight, int height, const int MAX_HEIGHT) {
  if (printLeft || printRight ||
  (node.left == null && node.right == null && height == MAX_HEIGHT)) {
    print node;
  }
  if (node.left) printBorder(node.left, printLeft, printRight && node.right==null)
  if (node.right) printBorder(node.right, printLeft && node.left == null, printRight)
}

Where MAX_HEIGHT found by maxdepth(root, 0);

int maxdepth(Node node, int height) {
  if (node == null) return height;
  return max(maxdepth(node.left, height+1), maxdepth(node.right, height+1))
}