Session 30: Binary Trees 4
Original Session
Date: 12 Jan 2025
Topic: Trees
Concept: Level order traversal
Programs
- 102. Binary Tree Level Order Traversal
- leetcode here
public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> output = new ArrayList(); if (root == null) { return output; } Queue<TreeNode> q = new LinkedList(); q.add(root); while (!q.isEmpty()) { ArrayList<Integer> list = new ArrayList(); int queSize = q.size(); for (int i=0; i<queSize; i++) { TreeNode element = q.remove(); list.add(element.val); if (element.left != null) { q.add(element.left); } if (element.right != null) { q.add(element.right); } } output.add(list); } return output; }
- 107. Binary Tree Level Order Traversal II
- leetcode here
public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> output = new ArrayList(); if (root == null) { return output; } Queue<TreeNode> q = new LinkedList(); q.add(root); while (!q.isEmpty()) { ArrayList<Integer> list = new ArrayList(); int queSize = q.size(); for (int i=0; i<queSize; i++) { TreeNode element = q.remove(); list.add(element.val); if (element.left != null) { q.add(element.left); } if (element.right != null) { q.add(element.right); } } output.add(list); } Collections.reverse(output); return output; }
- 199. Binary Tree Right Side View
- leetcode here
public List<Integer> rightSideView(TreeNode root) { List<Integer> output = new ArrayList(); if (root == null) { return output; } Queue<TreeNode> q = new LinkedList(); q.add(root); while (!q.isEmpty()) { int levelSize = q.size(); for (int i=0; i<levelSize; i++) { TreeNode element = q.remove(); // adding Only for last element if (i == levelSize-1) { output.add(element.val); } if (element.left != null) { q.add(element.left); } if (element.right != null) { q.add(element.right); } } } return output; }
- 103. Binary Tree Zigzag Level Order Traversal
- leetcode here
public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> output = new ArrayList(); if (root == null) { return output; } Queue<TreeNode> q = new LinkedList(); q.add(root); boolean flag = true; while (!q.isEmpty()) { ArrayList<Integer> list = new ArrayList(); int queSize = q.size(); for (int i=0; i<queSize; i++) { TreeNode element = q.remove(); list.add(element.val); if (element.left != null) { q.add(element.left); } if (element.right != null) { q.add(element.right); } } if (!flag) { Collections.reverse(list); } output.add(list); flag = !flag; } return output; }
- [HomeWork] Tree Boundary Traversal
- GFG here
class Solution { ArrayList<Integer> result = new ArrayList<>(); // Function to perform boundary traversal ArrayList<Integer> boundaryTraversal(Node root) { if (root == null) { return result; } // Add root data result.add(root.data); // Collect left boundary collectBoundaryLeft(root.left, result); // Collect leaf nodes collectLeaves(root.left, result); collectLeaves(root.right, result); // Collect right boundary List<Integer> rightBoundary = new ArrayList<>(); collectBoundaryRight(root.right, rightBoundary); result.addAll(rightBoundary); return result; } private void collectLeaves(Node root, List<Integer> result) { if (root == null) { return; } collectLeaves(root.left, result); // If it's a leaf node, add to result if (root.left == null && root.right == null) { result.add(root.data); } collectLeaves(root.right, result); } // Function to collect left boundary nodes // (top-down order) private void collectBoundaryLeft(Node root, List<Integer> result) { if (root == null) { return; } if (root.left != null) { result.add(root.data); collectBoundaryLeft(root.left, result); } else if (root.right != null) { result.add(root.data); collectBoundaryLeft(root.right, result); } } // Function to collect right boundary nodes // (bottom-up order) private void collectBoundaryRight(Node root, List<Integer> result) { if (root == null) { return; } if (root.right != null) { collectBoundaryRight(root.right, result); result.add(root.data); } else if (root.left != null) { collectBoundaryRight(root.left, result); result.add(root.data); } } }
- 116. Populating Next Right Pointers in Each Node
- leetcode here
// Recursive public Node connect(Node root) { if (root == null) { return root; } if (root.left != null) { root.left.next = root.right; } if (root.right != null) { root.right.next = root.next != null ? root.next.left : root.next; } connect(root.left); connect(root.right); return root; } // Iterative approach public Node connect(Node root) { if (root == null) { return root; } Node leftmost = root; while (leftmost.left != null) { Node head = leftmost; while (head != null) { head.left.next = head.right; if (head.next != null) { head.right.next = head.next.left; } head = head.next; } leftmost = leftmost.left; } return root; }
- 226. Invert Binary Tree
- leetcode here
// Recursive public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode temp = root.left; root.left = root.right; root.right = temp; invertTree(root.left); invertTree(root.right); return root; } //Iterative Approach
- 98. Validate Binary Search Tree
- leetcode here
class Solution { public boolean isValidBST(TreeNode root) { return helper(root, Long.MIN_VALUE, Long.MAX_VALUE); } boolean helper(TreeNode root, long minValue, long maxValue) { if (root == null) { return true; } if (root.val >= maxValue || root.val <= minValue) { return false; } return helper(root.left, minValue, root.val) && helper(root.right, root.val, maxValue); } }
- 235. Lowest Common Ancestor of a Binary Search Tree
- leetcode here
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { while (root != null) { if (root.val > p.val && root.val > q.val) { root = root.left; } else if (root.val < p.val && root.val < q.val) { root = root.right; } else { break; } } return root; }