The Fellow Programmer

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the left and right subtrees of  every  node differ in height by no more than 1. Example 1: Input: root = [3,9,20,null,null,15,7] Output: true Example 2: Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true   Constraints: The number of nodes in the tree is in the range  [0, 5000] . -10 4  <= Node.val <= 10 4 Solution: /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int ...

Given the   root   of a binary tree, the depth of each node is   the shortest distance to the root . Return  the smallest subtree  such that it contains  all the deepest nodes  in the original tree. A node is called  the deepest  if it has the largest depth possible among any node in the entire tree. The  subtree  of a node is tree consisting of that node, plus the set of all descendants of that node. Example 1: Input: root = [3,5,1,6,2,0,8,null,null,7,4] Output: [2,7,4] Example 2: Input: root = [1] Output: [1] Explanation: The root is the deepest node in the tree. Example 3: Input: root = [0,1,3,null,2] Output: [2] Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.   Constraints: The number of nodes in the tree will be in the range  [1, 500] . 0...

Given the   root   of a binary tree, return   its maximum depth . A binary tree's  maximum depth  is the number of nodes along the longest path from the root node down to the farthest leaf node. Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2 Example 3: Input: root = [] Output: 0 Example 4: Input: root = [0] Output: 1 Constraints: The number of nodes in the tree is in the range  [0, 10 4 ] . -100 <= Node.val <= 100 Solution 1: /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeN...

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree , but some nodes are null. The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation. Example 1: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: 4 Explanation: The maximum width existing in the third level with the length 4 (5,3,null,9). Example 2: Input: 1 / 3 / \ 5 3 Output: 2 Explanation: The maximum width existing in the third level with the length 2 (5,3). Example 3: Input: 1 / \ 3 2 / 5 Output: 2 Explanation: The maximum width ...

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7] , 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  * ...

Invert a binary tree. Example: Input: 4 / \ 2 7 / \ / \ 1 3 6 9 Output: 4 / \ 7 2 / \ / \ 9 6 3 1   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode() {}  *     TreeNode(int val) { this.val = val; }  *     TreeNode(int val, TreeNode left, TreeNode right) {  *         this.val = val;  *         this.left = left;  *         this.right = right;  *     }  * }  */ class Solution {     public TreeNode invertTree(TreeNode root) {     if (root == null) {     ...

In a binary tree, the root node is at depth 0 , and children of each depth k node are at depth k+1 . Two nodes of a binary tree are cousins if they have the same depth, but have different parents . We are given the root of a binary tree with unique values, and the values x  and y  of two different nodes in the tree. Return  true  if and only if the nodes corresponding to the values x and y are cousins.   Example 1: Input: root = [1,2,3,4] , x = 4 , y = 3 Output: false Example 2: Input: root = [1,2,3,null,4,null,5] , x = 5 , y = 4 Output: true Example 3: Input: root = [1,2,3,null,4] , x = 2, y = 3 Output: false   Note: The number of nodes in the tree will be between 2 and 100 . Each node has a unique integer value from 1 to 100 .   /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *...

Given a binary tree where each path going from the root to any leaf form a valid sequence , check if a given string is a valid sequence in such binary tree. We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree. Example 1: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,0,1] Output: true Explanation: The path 0 -> 1 -> 0 -> 1 is a valid sequence (green color in the figure). Other valid sequences are: 0 -> 1 -> 1 -> 0 0 -> 0 -> 0   Example 2: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,0,1] Output: false Explanation: The path 0 -> 0 -> 1 does not exist, therefore it is not even a sequence.   Example 3: Input: root = [0,1,0,0,1,0,null,null,1,0,0], arr = [0,1,1] Output: false Explanation: The path 0 -> 1 -> 1 is a seq...

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6   Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42       /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int result = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { findMax(root); return result; } int findMax(TreeNode root) { if (root == null) return 0; ...

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. Example: Given a binary tree 1 / \ 2 3 / \ 4 5 Return 3 , which is the length of the path [4,2,1,3] or [5,2,1,3]. Note: The length of path between two nodes is represented by the number of edges between them.  /**  * Definition for a binary tree node.  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ public class Solution {     int max = 0;        public int diameterOfBinaryTree(TreeNode root) {         depth(root);...