Binary tree print border

Question

How to print an external binary tree frame.

• order from top to bottom, left to right, then top to bottom
• print all left nodes and the most faithful nodes
• print all leaf nodes

• print all nodes that have only 1 sheet

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

for example: the output should be 100, 50, 24, 12, 30, 57, 60, 130, 132, 150

If we write three different functions for printing left nodes, leaf nodes and right nodes, they can be easily solved, but it will take O (n + 2logn) time.

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

Answer 1

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

Starting with root, do a roundup in order and check if it is equal to right , which means we never made a recursive call to the right. If yes, type node, that means we print all the left nodes of the tree. If right is not equal to zero, they are not considered borders, so find the nodes of the sheet and print them.

Bypassing Inorder, after the left subtree calls are completed, you go to the root, and then the recursive call for the right under the tree. Now first check that the nodes of the leaves are cleaned and printed, and then check to see if it is left , which means that we made a recursive call on the left, so they are not considered a border. If the left has a zero print node, this means that we print all the rightmost nodes of the tree.

Code snippet

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

}

Answer 2

Algo:

• print left border
• print leaves
• print right border

---

 void getBoundaryTraversal(TreeNode t) { System.out.println(tt); 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(tt); return; } traverseLeafs(t.left); traverseLeafs(t.right); } private void traverseLeftBoundary(TreeNode t) { if (t != null) { if (t.left != null) { System.out.println(tt); traverseLeftBoundary(t.left); } else if (t.right != null) { System.out.println(tt); traverseLeftBoundary(t.right); } } } private void traverseRightBoundary(TreeNode t) { if (t != null) { if (t.right != null) { traverseRightBoundary(t.right); System.out.println(tt); } else if (t.left != null) { traverseLeafs(t.left); System.out.println(tt); } } } 

---

TreeNode definition:

 class TreeNode<T> { private T t; private TreeNode<T> left; private TreeNode<T> right; private TreeNode(T t) { this.t = t; } } 

Answer 3

You can achieve this with the Euler algorithm applied to your tree. See Link:

Or (if you have access to it) a book by Goodrich et al. (Link here )

I hope this helps

Answer 4

Sounds like a domestic work problem, but I need practice. I have not done anything with recursion for 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; } } 

Answer 5

The decision can be made by moving the tree in a preliminary order - O (n).
Find the sample code below. Source and some explanations .

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

Answer 6

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

Answer 7

You can recursively go through each node and control when to print, here is a 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]);