CODEWITHSUNDEEP
algorithmbinary-tree
sachin
sachin

Reputation: 203

print boundary of binary tree

How to print the outside frame of a binary tree.

  1. the order is top to down, left to right, then down to top
  2. print all leftest node and rightest nodes
  3. print all leaf nodes

  4. print all nodes which only have 1 leaf

             100
        /   \ 
      50     150
     / \      /
   24   57   130
  /  \    \    \
12   30    60   132

e.g: the output should be 100, 50, 24, 12, 30, 57, 60, 130, 132, 150

If we write three different functions to print left nodes, leaf nodes and right nodes, it can be easily solved but it takes O(n+2logn) time.

I am also looking for an O(n) approach but condition is that each node should be visited only once, dont want this extra O(2logn) part.

Upvotes: 6

Views: 4607

Answers (7)

eguitarz
eguitarz

Reputation: 46

You can recursively go through every node and control when to print, here is the javascript code snippet.

function findBtreeBoundaries(arr, n, leftCount, rightCount) {
  n = n || 0;
  leftCount = leftCount || 0;
  rightCount = rightCount || 0;

  var length = arr.length;
  var leftChildN = 2*n + 1, rightChildN = 2*n + 2;

  if (!arr[n]) {
    return;
  }

  // this is the left side of the tree
  if (rightCount === 0) {
    console.log(arr[n]);
  }

  // select left child node
  findBtreeBoundaries(arr, leftChildN, leftCount + 1, rightCount);

  // this is the bottom side of the tree
  if (leftCount !== 0 && rightCount !== 0) {
    console.log(arr[n]);
  }

  // select right child node
  findBtreeBoundaries(arr, rightChildN, leftCount, rightCount + 1);

  // this is the right side of the tree
  if (leftCount === 0 && rightCount !== 0) {
    console.log(arr[n]);
  }

}

findBtreeBoundaries([100, 50, 150, 24, 57, 130, null, 12, 30, null, 60, null, 132]);

Upvotes: 0

Clay Schubiner
Clay Schubiner

Reputation: 131

Here's a simple solution:

def printEdgeNodes(root, pType, cType):
   if root is None:
       return
   if pType == "root" or (pType == "left" and cType == "left") or (pType == "right" and cType == "right"):
        print root.val
   if root.left is None and root.right is None:
       print root.val
   if pType != cType and pType != "root":
       cType = "invalid"
   printEdgeNodes(root.left, cType, "left")

def printEdgeNodes(root):
    return printEdgeNodes(root, "root", "root")

Upvotes: 0

Trying
Trying

Reputation: 14278

Algo:

  1. print the left boundary
  2. print the leaves
  3. print the right boundary
void getBoundaryTraversal(TreeNode t) {
        System.out.println(t.t);
        traverseLeftBoundary(t.left);
        traverseLeafs(t);
        //traverseLeafs(t.right);
        traverseRightBoundary(t.right);
    }
    private void traverseLeafs(TreeNode t) {
        if (t == null) {
            return;
        }
        if (t.left == null && t.right == null) {
            System.out.println(t.t);
            return;
        }
        traverseLeafs(t.left);
        traverseLeafs(t.right);
    }
    private void traverseLeftBoundary(TreeNode t) {
        if (t != null) {
            if (t.left != null) {
                System.out.println(t.t);
                traverseLeftBoundary(t.left);
            } else if (t.right != null) {
                System.out.println(t.t);
                traverseLeftBoundary(t.right);
            }
        }
    }

    private void traverseRightBoundary(TreeNode t) {
        if (t != null) {
            if (t.right != null) {
                traverseRightBoundary(t.right);
                System.out.println(t.t);
            } else if (t.left != null) {
                traverseLeafs(t.left);
                System.out.println(t.t);
            }
        }
    }

TreeNode definition:

class TreeNode<T> {

    private T t;
    private TreeNode<T> left;
    private TreeNode<T> right;

    private TreeNode(T t) {
        this.t = t;
    }
}

Upvotes: 1

user1712376
user1712376

Reputation: 514

The solution can be done by traversing the tree in pre-order - O(n).
Find sample code below. Source and some explanation.

Sample code in Java:

public class Main {
    /**
     * Prints boundary nodes of a binary tree
     * @param root - the root node
     */
    public static void printOutsidesOfBinaryTree(Node root) {

        Stack<Node> rightSide = new Stack<>();
        Stack<Node> stack = new Stack<>();

        boolean printingLeafs = false;
        Node node = root;

        while (node != null) {

            // add all the non-leaf right nodes left
            // to a separate stack
            if (stack.isEmpty() && printingLeafs && 
                    (node.left != null || node.right != null)) {
                rightSide.push(node);
            }

            if (node.left == null && node.right == null) {
                // leaf node, print it out
                printingLeafs = true;
                IO.write(node.data);
                node = stack.isEmpty() ? null : stack.pop();
            } else {
                if (!printingLeafs) {
                    IO.write(node.data);
                }

                if (node.left != null && node.right != null) {
                    stack.push(node.right);
                }
                node = node.left != null ? node.left : node.right;
            }
        }

        // print out any non-leaf right nodes (if any left)
        while (!rightSide.isEmpty()) {
            IO.write(rightSide.pop().data);
        }
    }
}

Upvotes: 0

Imposter
Imposter

Reputation: 2686

This can be done in O(n) .That is ,we visit each node of the tree only once. Logic is as follows Maintain two variables left and right and initialize them to zero. When ever there is recursive call to left side increment left by 1 When ever there is recursive call to ride side increment right by 1

Starting from root,do inorder traversal and check whether right is zero, that means we never made recursive call to right. If yes print node, this means we are printing all leftmost nodes of tree .If right is non zero , they are not considered as boundaries,so look for leaf nodes and print them .

In the Inorder traversal after left sub tree calls are done you bubble up to root and then we do recursive call for right sub tree. Now check for leaves nodes first and print them ,then check whether left is zero, that means we made recursive call to left ,so they are not considered as boundary. If left is zero print node, this means we are printing all rightmost nodes of tree .

The code snippet is

void btree::cirn(struct node * root,int left,int right)
{



 if(root == NULL)
    return;
if(root)
{

    if(right==0)
    {

        cout<<root->key_value<<endl;
    }

     cirn(root->left,left+1,right);




if(root->left==NULL && root->right==NULL && right>0)
    {

            cout<<root->key_value<<endl;
    }





  cirn(root->right,left,right+1);
  if(left==0)
   {

       if(right!=0)
      {
            cout<<root->key_value<<endl;
       }


   }




}

}

Upvotes: 3

jlunavtgrad
jlunavtgrad

Reputation: 1015

Seems like a home work problem, but I need the practice. I haven't done anything with recursion in a decade.

void SimpleBST::print_frame()
{
   if (root != NULL)
   {
      cout << root->data;

      print_frame_helper(root->left, true, false);
      print_frame_helper(root->right, false, true);
      cout << endl;
   }
}

void SimpleBST::print_frame_helper(Node * node, bool left_edge, bool right_edge)
{
   if (node != NULL)
   {
      if (left_edge)
         cout << ", " << node->data;

      print_frame_helper(node->left, left_edge && true, false);

      if ((!left_edge) && (!right_edge))
         if ((node->left == NULL) || (node->right == NULL))
            cout << node->data << ", ";

      print_frame_helper(node->right, false, right_edge && true);

      if (right_edge)
         cout << ", " << node->data;
   }
}

Upvotes: 0

gmazlami
gmazlami

Reputation: 694

You may achieve that with the Euler Tour algorithm applied to your tree. See this link:

Or (if have access to it) the book of Goodrich et. al (link. here )

I hope this helps

Upvotes: 0

Related Questions