1. Full (Proper) Binary Tree # Each nodes has either 2 or 0 children. 12 8 18 5 11 2. Degenerate (Pathological) Binary Tree # Each internal node has either a right or a left child. # Each node is a left node or each node is a right node. 1 1 2 2 3 3 4. Complete Binary Tree # Each level is filled from left to right. 8 5 3 4 6 7 5....
Problem Statement 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: 3 9 20 15 7 Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2 Key Insights We can Recursive Solution # Definition for a binary tree node....
Problem Statement Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level). Example 1: 3 9 20 16 7 Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] Example 2: Input: root = [1] Output: [[1]] Example 3: Input: root = [] Output: [] Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self....
Problem Statement Given a binary tree, determine if it is height-balanced A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one. Example 1: 3 9 20 15 7 Input: root = [3,9,20,null,null,15,7] Output: true Example 2: 1 2 2 3 3 4 4 Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true Key Insights A binary tree is considered height balanced if the height differences between the left and right subtrees are less than or equal to one....
Problem Statement Given the root of a binary tree, invert the tree, and return its root. Example 1: 4 4 ----> 2 7 7 2 1 3 6 9 9 6 3 1 Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1] Example 2: Input: root = [2,1,3] Output: [2,3,1] Example 3: Input: root = [] Output: [] Key Insights If you can swap every node’s left and right children, you can “invert” the binary tree....