Binary Tree Border Search

Question

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

So if a binary tree

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

He must print 50 25 15 35 120 155 250 20 150 10.

If the binary tree

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

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

How can I do that? Does this generalization for a binary tree explain a more complicated problem?

Any help via links would also be appreciated.

PS: look that the pattern does not start from the root, but to the left (in this case). It may also begin with the right, but it always ends with the root.

Answer 1

, , - , node / , : 1) node node 2) node " " , " "

A node " ", node, ( ) node ( left) node, " ", ( ) .

, DFS, .

Answer 2

, . , .

, node, . , , .

, , , . , .

Answer 3

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;
  }
}

Answer 4

, , .

printBorder (, , ) . : , .

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)
}

MAX_HEIGHT 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))
}