Binary Tree

14 flashcards · Other · by Steven Bui

1. 104. Maximum Depth of a Binary Tree Given the root of a binary tree, return its maximum depth (including the root node). ex. Input: root = [3, 9, 20, null, null, 15, 7] Output: 3 ---------------------------------------------------------------------------------- public int method (TreeNode root) { .... } public class TreeNode { ....int val; ....TreeNode left; ....TreeNode right; }

   Approach: You want to use a recursive approach. First, create a base case: if the current node is null, then return 0. Then, create the recursive case: call the method on the node's left node, and save it in a variable. Then, call the method on the node's right node, and save it in a variable. Since you know that your current node is not null (as checked by the base case), return 1 + the maximum of the left and right variables. Code: public int method (TreeNode root) { ....if (root == null) ...…

2. 100. Are the Binary Trees Identical Given the roots of two binary trees p and q, return true if they are exactly the same and false otherwise. Having the same nodes but flipped does NOT count as being identical. ex. Input: p = [1, 2, 3], and q = [1, 2, 3] Output: true ---------------------------------------------------------------------------------- public boolean method (TreeNode p, TreeNode q) { .... }

   Approach: You want to use a recursive approach. First, create a base case: if both p and q are null, then they are both at an end node, so return true. Then, create the recursive case: since the base case ensured that the nodes cannot both be null, if either p or q are null, then return false. Likewise, if their values are different, return false. Return this method being called on both p and q's left nodes, AND the method being called on their right nodes. Code: public boolean method (TreeNode…

3. 101. Are the Children Mirrors of Themselves Given the root of a binary tree, return true if the children are mirrors of themselves, meaning that it is symmetric around the root node. ex. Input: [1, 2, 2, 3, 4, 4, 3] Output: true ---------------------------------------------------------------------------------- public boolean method (TreeNode root) { .... }

   Approach: You want to use a recursive approach. However, since you want to check the left and right nodes, calling recursion on this method will NOT work. Instead, create a helper method. First, still in this method, check if the left and right nodes are null. If not, then call the recursive method on the left and right children. First, create a base case: if both left and right are null, then they are both at an end node, so return true. After that, since the base case ensured that the nodes c…

4. 226. Flip Binary Tree Over Y-Axis Given the root of a binary tree, invert the tree (basically flipping it over the y-axis) and return the root. ex. Input: [4, 2, 7, 1, 3, 6, 9] Output: [4, 7, 2, 9, 6, 3, 1] ---------------------------------------------------------------------------------- public TreeNode method (TreeNode root) { .... }

   Approach: You want to use a recursive approach. If you look at the picture, all you have to do is swap the children in each subtree. First, create a base case: if the root is null, return null. Then, create a recursive case: call this method on the left child, and then on the right children, and save the returned nodes in variables. Then, swap the children of the current node since that is what it means to invert the tree. Return the root at the end. Code: public TreeNode method (TreeNode root)…

5. 112. Does Any Path Add Up to a Sum Given the root of a binary tree and a target integer targetSum, return true if there is any path from the root node to a leaf node (i.e. the last node in a path) that exactly adds up to targetSum. ex. Input: root = [5, 4, 8, 11, ...], and targetSum = 22 Output: true (5 + 4 + 11 + 2 = 22) ---------------------------------------------------------------------------------- public int method (TreeNode root, int targetSum) { .... }

   Approach: You want to use a recursive approach. You will call this method over and over, decreasing targetSum on each iteration. First, create a base case: if the root is null, return false. If it is not null, then check is it is the last node in the path (i.e. both children are null). If its value is equal to targetSum, return true. Then, create the recursive case: set the new target value to targetSum minus the current node's value, and call this method on the left and right children with the…

6. 129. Add Up Root-to-Leaf Numbers Given the root of a binary tree, say each path from root to leaf creates a number (ex. 1 -> 2 -> 3 creates 123). Return the total sum of all paths. ex. Input: root = [1, 2, 3] Output: 25 (12 + 13 = 25) ---------------------------------------------------------------------------------- public int method (TreeNode method) { .... }

   Approach: You want to use a recursive approach. Since you need to keep track of the sum, you need to create a helper method with a TreeNode and integer parameter. First, in the main method, call the helper method on the root and 0 (0 representing the tens place right now, where the root itself is just 1 digit). Then, in the helper method, create a base case: if the root is null, return 0. After that, set the integer to 10 * sum, plus the root's value. Then, if the root is an end node, return th…

7. 114. Binary Tree to an Unbalanced Tree (in Pre-Order) Given the root of a binary tree, use pre-order traversal (add the node as you touch it on the LEFT side) to edit the tree so that each node's right node is the next node in the pre-order traversal (and the left node is always null). ex. Input: Output: ---------------------------------------------------------------------------------- public void method (TreeNode root) { .... }

   Approach: You want to use a recursive approach. The trick is to look at each left node: if you set the node's left child to be the new right child and then attach the old right child as the child of the new right child, you end up with the unbalanced tree that you want. First, create a base case: if the node is null, just return. Then, create a recursive case: call this method on the node's left child, and then the node's right child (this is pre-order traversal since we start with the left, th…

8. 236. Lowest Common Parent Given the root of a binary tree and 2 other nodes p and q, return the node that is the lowest (aka as far from the root as possible) node that both nodes have as a common parent. A node can be its own parent. ex. Input: p = 5, and q = 1 Output: 3 (3 is the common parent of nodes 5 and 1) ---------------------------------------------------------------------------------- public TreeNode method (TreeNode root, TreeNode p, TreeNode q) { .... }

   Approach: You want to use a recursive approach. The trick is to realize that when we traverse the tree, once we find a node that is either p or q, we want to return that node immediately (to make the variable from the recursive call not null). First, create the base case: if the root is either p, q, or null, return the root. If it is p or q, then this base case returns a non-null value to the recursive call. If it is null, then this returns null. Then, create the recursive case: call this metho…

9. 199. Binary Tree Right Side Given the root of a binary tree, return the nodes that you can see from top to bottom if you are looking at it from the right side. ex. Output: [1, 3, 4] ---------------------------------------------------------------------------------- public List<Integer> method (TreeNode root) { .... }

   Approach: You want to use a recursive approach. You have to use depth-first search, which basically keeps going down the right side until it hits a null node, after which it goes back up and checks the left side. First, create a base case: if the root is null, return an empty list. After that, call a helper method that keeps track of the current node, the depth level, and the list being returned. Then, create a base case for the helper method: if you are encountering this depth for the first ti…

10. 637. Average of Each Level in a Binary Tree Given the root of a binary tree, return the average value of each level in the form of an array. ex. Output: [3, 14.5, 11] ---------------------------------------------------------------------------------- public List<Double> method (TreeNode root) { .... }

    Approach: You are going to want to use a level-order traversal, also known as breadth-first search, which uses a Queue of nodes (add = offer(), remove = poll()). In a while-loop while the queue is not empty, the trick is to remember that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. In a for-loop inside of the while-loop that runs for the number of nodes in the level, get the node's value, add it to a sum variable, and add the children to the…

11. 102. Level Order Traversal Given the root of a binary tree, return the level order traversal of the tree, except you return a list of ArrayLists<Integer>, where each internal ArrayList holds the contents of each level. ex. Output: [ [3], [9, 20], [15, 7] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (TreeNode root) { .... }

    Approach: You are going to want to use a level-order traversal, also known as breadth-first search, which uses a Queue of nodes (add = offer(), remove = poll()). In a while-loop while the queue is not empty, the trick is to remember that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. Right before you go into a for-loop inside of the while-loop that runs for the number of nodes in the level, create an ArrayList to add the contents of the level i…

12. 103. Level Order Traversal Zig-Zagged Given the root of a binary tree, return the level order traversal of the tree as a list of ArrayLists<Integer>, except the first list order goes left-to-right, the next list order goes right-to-left, and we alternate this pattern. ex. Output: [ [3], [20, 9], [15, 7] ] ---------------------------------------------------------------------------------- public List<List<Integer>> method (TreeNode root) { .... }

    Approach: You are going to want to use a level-order traversal, also known as breadth-first search, which uses a Queue of nodes (add = offer(), remove = poll()). Before the while-loop, create a boolean value to keep track of whether to order the list left-to-right or not. In a while-loop while the queue is not empty, the trick is to remember that when you do queue.size() at the beginning of the loop, you get the number of nodes in that level. Right before you go into a for-loop inside of the wh…

13. 98. Is the Binary SEARCH Tree Valid Given the root of a binary tree, return true if the tree is a valid binary search tree (meaning left children are less than the node, and right children are greater than the node). ex. Output: false (3 is not between 4 and 5) ---------------------------------------------------------------------------------- public boolean method (TreeNode root) { .... }

    Approach: You want to use a recursive approach. You need to create a helper method that takes the minimum and maximum valid values in a range. First, in the main function, call the helper method using the smallest and largest values possible. Then, create a base case: if the root is null, return true. If the root's value is NOT between the maximum and minimum values, the return false. Then, create a recursive case: call the helper function on the node's left child while changing max to the curr…

14. 104. Maximum Depth of a Binary Tree Given the root of a binary tree, return its maximum depth (including the root node). ex. Input: root = [3, 9, 20, null, null, 15, 7] Output: 3 ---------------------------------------------------------------------------------- public int method (TreeNode root) { .... } public class TreeNode { ....int val; ....TreeNode left; ....TreeNode right; }

    Approach: You want to use a recursive approach. First, create a base case: if the current node is null, then return 0. Then, create the recursive case: call the method on the node's left node, and save it in a variable. Then, call the method on the node's right node, and save it in a variable. Since you know that your current node is not null (as checked by the base case), return 1 + the maximum of the left and right variables. Code: public int method (TreeNode root) { ....if (root == null) ...…