Binary Tree Flashcards
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.
Base case of null node - return 0. To calculate next node up, return (1 + max(root.left, root.right))
O(n) / O(n)
Given the roots of two binary trees p and q, write a function to check if they are the same or not.
Two binary trees are considered the same if they are structurally identical, and the nodes have the same value
Base cases: bunch of booleans comparing the trees. Both are null: True, p or q is null: False, p.val != q.val: False, then recursive call
O(p + q) / Space? Probably nothing because you’re not storing any nodes
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Given the root of a binary tree, invert the tree, and return its root.
Base case: null node returns None. Then swap left and right of the root, then do recursive calls on right and left subtrees.
invert tree
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
temp = root.left
root.left = root.right
root.right = temp
self.invertTree(root.right)
self.invertTree(root.left)
return root
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.
def isSubtree(root, sub)
Think about what happens when one or both trees are empty!!
If not sub, True, because empty tree is always subtree
If not root, return False because sub is not empty.
Check if root and sub are the same tree. Recursive call on left and right subtrees.
O(p * q) / O(p)
Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Key logic: if p and q are in opposite sides of the root, return the root. Otherwise go left or right based on if p and q are > or < the root.
O(logn) / O(1)
LCA IS NOT A DFS OR BFS PROBLEM it’s just a matter of intelligently navigating the BST tracking a current node
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).
BFS but calc the length of each level (len(queue)) and use inner for loop to loop through number of nodes in that level.
O(n) / O(n/2) -> O(n)
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left
subtree
of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
Recursive DFS, pass upper and lower bounds in the function to track the root value.
Then check if out of bounds every time you go down the tree. Also consider that nodes cannot be equal.
Recursive call on L and R, updating bounds.
O(n) / O(1)
valid BST
def isValid(root, lower, upper):
if not root:
return True
if root.val >= upper or root.val <= lower:
return False
return (isValid(root.right, root.val, upper) and
isValid(root.left, lower, root.val))
return isValid(root, -math.inf, math.inf)
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Do INORDER TRAVERSAL with iterative DFS,
- “while stack or current”,
- inner while loop to go all the way left and add each node to the stack
- start popping from the stack tracking num of pops
- set current to current.right (so the inner while loop can run again)
- loop until you pop k times.
O(n) / O(n)
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
current = root
n = 0
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
n += 1
if n == k:
return current.val
current = current.right
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Trick: preorder always gives you the root, inorder gives you the nodes to the left and right of the root. Base case, if either of the traversal lists are empty. Create root and set left and right using recursive calls of same function
O(n^2) / O(n) because of index()
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.
The path sum of a path is the sum of the node’s values in the path.
Given the root of a binary tree, return the maximum path sum of any non-empty path.
Set a global variable as a list that tracks the maxPath at any given point in time. Write a recursive DFS function that traverses left and right. If left or right is negative, set it to 0 so it’s ignored. Check the maxPath at the current node (includes the “split” so root + left + right). Return the not splitting max path (root.val + max(left, right)
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Recursive DFS to convert tree into a list, including ‘null’. Set global variable i, then Recursive DFS to go through the list, and set right and left nodes.
Iterative DFS on binary tree, add values to a list.
def iterativeDFS():
if a == None:
return []
values = []
stack = [a] # intialize with root node
while len(stack) > 0:
current = stack.pop()
values.append(current.val)
if current.right: # push right first so when you pop, left is on top
stack.append(current.right)
if current.left:
stack.append(current.left)
return values
Recursive DFS on binary tree, add values to list.
def recursiveDFS(root):
if root == None:
return []
leftValues = recursiveDFS(root.left)
rightValues = recursiveDFS(root.right)
return [root.val] + leftValues + rightValues
Iterative BFS on binary tree, add values to list.
def iterativeBFS(root):
if not root:
return []
queue = [root]
values = []
while len(queue) > 0:
current = queue.pop(0)
values.append(current.val)
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return values
Inorder traversal
left, root, right (go all the way left, before going to root)
https://opendsa-server.cs.vt.edu/embed/btTravinorderPRO
