Binary tree border print

Question

I was asked in an interview to print the border of a binary tree. For example.

1 / \ 2 3 / \ / \ 4 5 6 7 / \ \ 8 9 10 

The answer will be: 1, 2, 4, 8, 9, 10, 7, 3

I gave the following answer.

First method:

I used the Bool variable to solve the above problem.

 void printLeftEdges(BinaryTree *p, bool print) { if (!p) return; if (print || (!p->left && !p->right)) cout << p->data << " "; printLeftEdges(p->left, print); printLeftEdges(p->right, false); } void printRightEdges(BinaryTree *p, bool print) { if (!p) return; printRightEdges(p->left, false); printRightEdges(p->right, print); if (print || (!p->left && !p->right)) cout << p->data << " "; } void printOuterEdges(BinaryTree *root) { if (!root) return; cout << root->data << " "; printLeftEdges(root->left, true); printRightEdges(root->right, true); } 

His answer: you have used the Bool variable so many times. Can you solve it without using it.

Second method:

I just used tree traversal to solve this problem.

 1. Print the left boundary in top-down manner. 2. Print all leaf nodes from left to right, which can again be sub-divided into two sub-parts: 2.1 Print all leaf nodes of left sub-tree from left to right. 2.2 Print all leaf nodes of right subtree from left to right. 3. Print the right boundary in bottom-up manner. 

His answer: he, too, was not satisfied with this method. He said that you cross a tree 3 times . That's too much. Give a different solution if you have one.

Third method: This time I went to Order Bypass (BFS) .

  1: Print starting and ending node of each level 2: For each other node check if its both the children are <b>NULL</b> then print that node too. 

His answer: he was also not happy with this method, because this method takes additional memory of order O (n).

My question is: tell me the method that traverses the tree once, do not use the Bool variable and do not use extra memory. Is it possible?

Answer 1

I guess this should do the trick:

 traverse(BinaryTree *root) { if (!root) return; cout << p->data << " "; if (root->left ) traverseL(root->left ); //special function for outer left if (root->right) traverseR(root->right); //special function for outer right } traverseL(BinaryTree *p) { cout << p->data << " "; if (root->left ) traverseL(root->left ); //still in outer left if (root->right) traverseC(root->right); } traverseR(BinaryTree *p) { if (root->left ) traverseC(root->left ); if (root->right) traverseR(root->right); //still in outer right cout << p->data << " "; } traverseC(BinaryTree *p) { if (!root->left && !root->right) //bottom reached cout << p->data << " "; else { if (root->left ) traverseC(root->left ); if (root->right) traverseC(root->right); } } 

Start with the traverse function. Selected zero requests at the beginning of each method (avoids one function call at each end). No bool variables are needed, it just uses three different workarounds:

• one for the left edge, displaying node before traversing
• one for the right edge outputting node after traversal
• one for all other nodes, outputting node if there are no siblings.

Answer 2

Below is a recursive solution in Python3 with O (n) time complexity. The algorithm here is to print most nodes from top to bottom on the left, leaf nodes from left to right and right in most nodes from bottom to top. Adding Boolean flags (isLeft,isRight) to bypass the left and right trees simplifies the code and controls the O (n) time complexity.

 #Print tree boundary nodes def TreeBoundry(node,isLeft,isRight): #Left most node and leaf nodes if(isLeft or isLeaf(node)): print(node.data,end=' ') #Process next left node if(node.getLeft() is not None): TreeBoundry(node.getLeft(), True,False) #Process next right node if(node.getRight() is not None):TreeBoundry(node.getRight(), False,True) #Right most node if(isRight and not isLeft and not isLeaf(node)):print(node.data,end=' ') #Check is a node is leaf def isLeaf(node): if (node.getLeft() is None and node.getRight() is None): return True else: return False #Get started #https://github.com/harishvc/challenges/blob/master/binary-tree-edge-nodes.py TreeBoundry(root,True,True) 

Answer 3

Method O(n) No extra space and single traversal of tree.

I divided the tree nodes into four types of nodes

Type 1 → Nodes that form the left border (e.g. 8)

Type 0 → Nodes that do not form borders (for example, 12)

Type 3 → Nodes that form the right border (e.g. 22)

Leaf nodes (e.g. 4,10,14)

In my method, I just do a recursive tree traversal method (just modified) where my function has this form

  void recFunc(btNode *temp,int type) { //Leaf Nodes if((temp->left == NULL)&&(temp->right == NULL)) cout << temp->data << " "; // type -1 Nodes must be printed before their children else if(type == 1)cout << temp->data << " "; else {;} if(type == 3) { if(temp->left)recFunc(temp->left,0); if(temp->right)recFunc(temp->right,3); //type 3 nodes must be printed after their children cout << temp->data << " "; } else if(type == 1) { if(temp->left)recFunc(temp->left,1); if(temp->right)recFunc(temp->right,0); } else if(type == 0) { if(temp->left)recFunc(temp->left,0); if(temp->right)recFunc(temp->right,0); } else {;} } 

where am i modofied

• In my recursive function, Type 1 nodes must make their left nodes as Type 1, and must be printed before calling their children (if they exist)
• Type 3 units should be printed in reverse order. Therefore, they should be printed after calling their children. They also need the right kids like type 3 nodes
• Type 0 nodes should not be printed, and they assign their children as type 0 Nodes
• Leaf nodes must be directly printed and returned.

Code Link

Answer 4

// 4 lists of differences for 4 different parts of the solution 1) left border 2) right border 3) leaf in the left tree 4) leaf in the right tree

 public class PRintBinaryTreeBoundary { ArrayList<TreeNode> leftBorderList=new ArrayList<>(); ArrayList<TreeNode> leftLEafNode=new ArrayList<>(); ArrayList<TreeNode> rightBorderList=new ArrayList<>(); ArrayList<TreeNode> rightLEafNode=new ArrayList<>(); public static void main(String[] args) { // TODO Auto-generated method stub /* 1 / \ 2 3 / \ / \ 4 5 6 7 / \ \ 8 9 10*/ TreeNode one=new TreeNode(1); TreeNode two=new TreeNode(2); TreeNode three=new TreeNode(3); TreeNode four=new TreeNode(4); TreeNode five=new TreeNode(5); TreeNode six=new TreeNode(6); TreeNode seven=new TreeNode(7); TreeNode eight=new TreeNode(8); TreeNode nine=new TreeNode(9); TreeNode ten=new TreeNode(10); one.left=two; one.right=three; two.left=four;two.right=five; three.left=six;three.right=seven; five.left=eight; six.right=nine; seven.right=ten; PRintBinaryTreeBoundary p=new PRintBinaryTreeBoundary(); p.print(one); } private void print(TreeNode one) { System.out.println(one.val); populateLeftBorderList(one.left); populateRightBorderList(one.right); populateLeafOfLeftTree(one.left); populateLeafOfRightTree(one.right); System.out.println(this.leftBorderList); System.out.println(this.leftLEafNode); System.out.println(this.rightLEafNode); Collections.reverse(this.rightBorderList); System.out.println(this.rightBorderList); } private void populateLeftBorderList(TreeNode node) { TreeNode n = node; while (n != null) { this.leftBorderList.add(n); n = n.left; } } private void populateRightBorderList(TreeNode node) { TreeNode n = node; while (n != null) { this.rightBorderList.add(n); n = n.right; } } private void populateLeafOfLeftTree(TreeNode leftnode) { Queue<TreeNode> q = new LinkedList<>(); q.add(leftnode); while (!q.isEmpty()) { TreeNode n = q.remove(); if (null == n.left && null == n.right && !this.leftBorderList.contains(n)) { leftLEafNode.add(n); } if (null != n.left) q.add(n.left); if (null != n.right) q.add(n.right); } } private void populateLeafOfRightTree(TreeNode rightNode) { Queue<TreeNode> q = new LinkedList<>(); q.add(rightNode); while (!q.isEmpty()) { TreeNode n = q.remove(); if (null == n.left && null == n.right && !this.rightBorderList.contains(n)) { rightLEafNode.add(n); } if (null != n.left) q.add(n.left); if (null != n.right) q.add(n.right); } } }