University:
Princeton University
Course:
COS 226 | Algorithms and Data Structures
Academic year:

2022
Views:

66

Pages:

8
Author:

Alexa Livingston

Boundary Traversal of Binary Tree Boundary Traversal of Binary Tree Given a binary tree, print boundary nodes of the binary tree Anti-Clockwise starting from the root. The boundary includes 1. left boundary (nodes on left excluding leaf nodes) 2. leaves (consist of only the leaf nodes) 3. right boundary (nodes on right excluding leaf nodes) Boundary Traversal of Binary Tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java.util.*; import java.util.Map.Entry; class Node { int data; Node left, right; public Node(int data){ this.data = data; left = right = null; } } class Main { static Node root; private List path1 = new ArrayList<>(); private List path2 = new ArrayList<>(); static Node build(String s[]){ if(s[0]=="N"||s.length==0) return null; Node root=new Node(Integer.parseInt(s[0])); Queue q=new LinkedList(); q.add(root); 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 int i=1; while(!q.isEmpty() && i= s.length) break; cval = s[i]; if(!cval.equals("N")){ int h=Integer.parseInt(cval); curr.right=new Node(h); q.add(curr.right); } i++; } return root; } 45 //print the leaves void printLeaves(Node node){ 46 if (node == null) 47 return; 48 printLeaves(node.left); 49 if (node.left == null && node.right == null) 50 System.out.print(node.data + " "); 51 printLeaves(node.right); 52 } 53 54 //left boundary void printBoundaryLeft(Node node){ 55 if (node == null) 56 return; 57 if (node.left != null) { 58 System.out.print(node.data + " "); 59 printBoundaryLeft(node.left); 60 } 61 else if (node.right != null) { 62 System.out.print(node.data + " "); 63 printBoundaryLeft(node.right); 64 } 65 } 66 67 //right boundary void printBoundaryRight(Node node){ 68 if (node == null) 69 return; 70 if (node.right != null) { 71 printBoundaryRight(node.right); 72 System.out.print(node.data + " "); 73 } 74 else if (node.left != null) { 75 printBoundaryRight(node.left); 76 System.out.print(node.data + " "); 77 } 78 } 79 void printBoundary(Node node){ 80 if (node == null) 81 return; 82 System.out.print(node.data + " "); 83 printBoundaryLeft(node.left); 84 printLeaves(node.left); 85 printLeaves(node.right); 86 printBoundaryRight(node.right); 87 } 88 89 //main method public static void main(String[] args){ 90 Scanner sc=new Scanner(System.in); 91 int i; 92 Main ob = new Main(); 93 String s[]=sc.nextLine().split(" "); 94 root = build(s); 95 ob.printBoundary(root); 96 } 97 98 } 99 100 101 102 103 104 105 106 107 108 109 110