Binary Tree, LeetCode
Full Binary Tree (Proper Binary Tree)
- every node has either exactly two children or no children.
Perfect Binary Tree (Strictly Full Binary Tree):
- Every internal node has two children
- All leaf nodes appear at the same depth(level).
- Level (k) start from 0
- Every level has
2^knodes (Level(k) start from 0). - Total nodes:
2^(k+1) - 1.
- Every level has
- Level (k) start from 1
- Every level has
2^(k - 1). nodes (Level(k) start from 0) - Total nodes:
2^(k) - 1.
- Every level has
Complete Binary Tree:
- Every level, except possibly the last, is completely filled.
- In the last level, all nodes are as far left as possible, with no “gaps” between them.
- heap is a complete binary tree.
Binary Search Tree:
- Average case for search and insert: O(log n) when the tree is approximately balanced (each comparison eliminates about half of the remaining nodes).
- Worst case for search and insert: O(n) if the tree becomes completely unbalanced (degenerates into a chain).
- Left -> Small, Top -> Medium, Right -> Big
- No requirement for node structure
Balanced Binary Search Tree:
- ∀ N: height(N.left) – height(N.right) ≤ 1
- the basic of map and set (the key in map and the element in set is in order)
# Initialization by Linked List:
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
# Initialization by List:
list = []
curr: list[index]
left_children: list[2 * index + 1]
right_children: list[2 * index + 2]
Using backtracking to build binary tree
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
nums = [1, 2, 3, 4, 5]
def list_to_complete_binary_tree(nums: List[int], i = 0):
if i > len(nums) - 1:
return
node = ListNode(nums[i])
node.left = list_to_complete_binary_tree(nums, i * 2 + 1)
node.right = list_to_complete_binary_tree(nums, i * 2 + 2)
return node
DFS:
# result should be the input of dfs, so that every recursive call will write into the same list
# pre-order
def dfs(self, result, root):
if not root:
return
result.append(root.val) # middle
left_branch = dfs(result, root.left) # left
right_branch = dfs(result, root.right) # right
return result
BFS
from collections import deque
def bfs(self, root):
if not root:
return []
queue = deque([root]) # queue stores node instead of the value of node
result = []
while queue:
length_of_level = len(queue)
level = []
for i in range(length_of_level):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
144. Binary Tree Preorder Traversal
# 1: _dfs accept result as input
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: Optional[List]) -> List[int]:
return self._dfs(result = [], root = root) if root else []
def _dfs(self, result: List[int], root: Optional[List]) -> List[int]:
if not root:
return # stop iteration
result.append(root.val)
left_branch = self._dfs(result, root.left)
right_branch = self._dfs(result, root.right)
return result
# 2. _dfs doesn't accept result as input
class Solution:
def preorderTraversal(self, root: Optional[List]) -> List[int]:
if not root:
return [] # return value
left = self.preorderTraversal(root.left) # return the value of left_branch
right = self.preorderTraversal(root.right)
return [root.val] + left + right # left and right are all list
145. Binary Tree Postorder Traversal
from typing import Optional, List
class ListNode:
def __ini__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: Optional[ListNode]) -> ListNode:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right from typing import Optional, List
class ListNode:
def __ini__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: Optional[ListNode]) -> ListNode:
if not root:
return []
left = self.postorderTraversal(root.left)
right = self.postorderTraversal(root.right)
return left + right + [root.val]
# Or
class Solution:
def postorderTraversal(self, root: Optional[ListNode]) -> ListNode:
return self._dfs(result = [], root = root) if root else [] # in case _dfs only run the first two line code
def _dfs(self, result, root) -> List[int]:
if not root:
return
left_branch = self._dfs(result, root.left)
right_branch = self._dfs(result, root.right)
result.append(root.val)
return result
94. Binary Tree Inorder Traversal
from typing import List, Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.right = right
self.left = left
class Solution:
def inorderTraversal(self, root: Optional[ListNode]) -> List[int]:
return self._dfs(result = [], root = root) if root else []
def _dfs(self, result, root) -> List[int]:
if not root:
return
left_branch = self._dfs(result, root.left)
result.append(root.val)
right_branch = self._dfs(result, root.right)
return result
# Or
class Solution:
def inorderTraversal(self, root: Optional[ListNode]) -> List[int]:
if not root:
return []
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
return left + [root.val] + right
102. Binary Tree Level Order Traversal
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[ListNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
result = []
while queue:
length_of_level = len(queue)
level = []
for _ in range(length_of_level):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
from typing import List, Optional
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None # Al
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
# Using parallel assignment in python
# temp = node.left
# node.left = node.right
# node.right = temp
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return root
len(nums) is even:
-
len(nums) // 2returns the left middle index. -
math.ceil(nums / 2)returns the right middle index.
len(nums) is odd:
- both return the middle one
queue could also store a tuple (node.left, node.right)
from typing import List, Optional
from collections import deque
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def isSymmetric(self, root: Optional[ListNode]) -> bool:
if not root:
return True
queue = deque([(root.left, root.right)])
while queue:
left, right = queue.popleft()
if not left and not right:
continue
if not left or not right or left.val != right.val:
return False
queue.append((left.left, right.right))
# compare whether the whole tree is symmetric
# queue.append((left.left, left.right)): compare the left branch of left is symmetric or not
queue.append((right.left, left.right))
return True
104. Maximum Depth of Binary Tree
from collections import deque
from typing import Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxDepth(self, root: Optional[ListNode]) -> int:
if not root:
return 0
queue = deque([root])
depth = 0
while queue:
depth += 1
length = len(queue)
for _ in range(length):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return depth
# In most problems, it doesn't matter whether
# you place operations like +1, updates,
# or returns at the beginning or end of a loop.
# Confused about the initial value of depth? move the position (beginning is more reasonable)
111. Minimum Depth of Binary Tree
leaf node: both node.left and node.right are None
from collections import deque
from typing import Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.right = right
self.left = left
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
queue = deque([root])
depth = 0
while queue:
depth += 1
length = len(queue)
level = []
for _ in range(length):
node = queue.popleft()
if node and not node.left and not node.right:
return depth
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
222. Count Complete Tree Nodes
from collections import deque
from typing import Optional
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.right = right
self.left = left
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
def getDepth(node):
if not node:
return 0
depth = 0
while node:
depth += 1
node = node.left
if not root:
return 0
depth_of_left_branch = getDepth(root.left) # getDepth is the method in countNodes, no need for self when using getDepth in countNodes
depth_of_right_branch = getDepth(root.right)
if depth_of_left_branch == depth_of_right_branch:
# the left branch is full
return 2^depth_of_left_branch - 1 + 1 + self.countNodes(root.right)
# + 1 is counting node itself
else:
# the right branch is full
return 2^depth_of_right_branch - 1 + 1 + self.counNodes(root.left)
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
"""
Some changes based on getDepth
def getDepth(node):
if not node:
return 0
left = getDepth(node.left)
# could be filled for the operations on left branch
right = getDepth(node.right)
# could be filled for the operations on right branch
# could be filled for the operation on current node
return max(left, right) + 1
"""
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1
return max(left, right) + 1
return check(root) != -1
Process currnt node
- update the state
- Add the node’s information into global state or the state passed as a parameter.
- path problem: state.path.append(node.val)
- sum problems: state.sum += node.val
- min/max problems: state.best = max(state.best, node.val)
- graph visits: state.visited.add(node)
- Add the node’s information into global state or the state passed as a parameter.
- Check or Record the result
- If the current state meets your goal, then save to your results list and optionally return/prune.
class ListNode: def __init__(self, val = 0, left = None, right = None): self.val = val self.left = left self.right = right class Solution: def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]: paths = [] def _dfs(node, path): if not node: return # ending condition:information to global state if not node.left and not node.right: paths.append(path) return if node.left: _dfs(node.left, path + '->' + str(node.left.val)) if node.right: _dfs(node.right, path + '->' + str(node.right.val)) if root: _dfs(root, str(root.val)) return paths
- If the current state meets your goal, then save to your results list and optionally return/prune.
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
_sum = 0
def _dfs(node):
nonlocal _sum
if not node:
return
if node.left and not node.left.left and not node.left.right:
# No matter whether node itself has a right child or not, it does not affect whether node.left is a leaf node.
_sum += node.left.val
_dfs(node.left)
_dfs(node.right)
_dfs(root)
return _sum
513. Find Bottom Left Tree Value
class ListNode:
def __init__(self, val = 0, left = None, right = None):
self.val = val
self.left = left
self.right = right
class Solution:
def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
queue = deque([root])
result = []
while queue:
length = len(queue)
level = []
for _ in range(length):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result[-1][0]
Enjoy Reading This Article?
Here are some more articles you might like to read next: