Session 31: Trees [Aman repeat session]

Original Session

Date: 16 Jan 2025

Topic: Trees

Concept: BST, all left values are less than root and right values are greater than root.

Programs

1. 173. Binary Search Tree Iterator
   1. leetcode here

   class BSTIterator {
   
       private Stack<TreeNode> stack = new Stack();
       private TreeNode root;
   
       public BSTIterator(TreeNode root) {
           this.root = root;
           while (root != null) {
               stack.add(root);
               root = root.left;
           }
       }
       
       public int next() {
           
           TreeNode node = stack.pop();
           
           TreeNode curr = node.right;
           while (curr != null) {
                   stack.add(curr);
                   curr = curr.left;
           }
           return node.val;
       }
       
       public boolean hasNext() {
           return !stack.isEmpty();
       }
   }

2. 199. Binary Tree Right Side View
   1. 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;
       }

3. 513. Find Bottom Left Tree Value
   1. leetcode here

   class Solution {
   
       public int findBottomLeftValue(TreeNode root) {
   
           int output = 0;
           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 == 0) {
                       output = element.val;
                   }
   
                   if (element.left != null) {
                       q.add(element.left);
                   }
   
                   if (element.right != null) {
                       q.add(element.right);
                   }
               }
           }
           return output;
       }
   }