Trees Flashcards
Validate Binary Search Tree (Medium)
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a 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.
helper(root, null, null) // lower, upper
if node = null, return true
if lower set and val <= lower return false
if upper set and val >= upper return false
if !helper(node.right, val, upper) return false
if !helper(node.left, lower, val) return false
return true
Time - O(n)
Space - O(n) / O(log n) average (height of tree)
Binary Tree Level Order Traversal (Medium)
Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
create traversal
push root node to queue
BFS, create level for each iteration for queue.length
push node to level
push left/right children if exist to queue
push level to traversal
Time - O(n)
Space - O(n)
Binary Tree Zigzag Level Order Traversal (Medium)
Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
create traversal
push root node to queue
set leftToRight to true
BFS, create level for each iteration for queue.length
if leftToRight, push node to level, otherwise unshift node to level
push left/right children if exist to queue
push level to traversal
Time - O(n)
Space - O(n)
Construct Binary Tree from Preorder and Inorder Traversal (Medium)
Given preorder and inorder traversal of a tree, construct the binary tree.
set preIndex = 0
iterate through inorder indexMap.set(inorder[i], i)
helper(0, inorder.length)
helper(inLeft, inRight) if inLeft = inRight return null rootVal = preorder[preIndex] root = new Node(rootVal) index = indexMap.get(rootVal) preIndex++ root.left = helper(inLeft, index) root.right = helper(index + 1, inRight) return root
Time - O(n)
Space - O(n)
Construct Binary Tree from Inorder and Postorder Traversal (Medium)
Given inorder and postorder traversal of a tree, construct the binary tree.
set postIndex = postorder.length - 1
iterate through inorder indexMap.set(inorder[i], i)
helper(0, inorder.length - 1)
helper(inLeft, inRight) if inLeft > inRight return null rootVal = postorder[postIndex] root = new Node(rootVal) index = indexMap.get(rootVal) postIndex-- root.right = helper(index + 1, inRight) root.left = helper(inLeft, index - 1) return root
Time - O(n)
Space - O(n)
Minimum Depth of Binary Tree (Easy)
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
set depth = 0
BFS
when you reach a leaf return depth
depth++ after each BFS cycle
Flatten Binary Tree to Linked List (Medium)
Given a binary tree, flatten it to a linked list in-place.
flattenTree(root)
if node = null return null
if node.left = null and node.right = null return node
leftTail = flattenTree(node.left)
rightTail = flattenTree(node.right)
if leftTail
leftTail.right = node.right
node.right = node.left
node.left = null
return rightTail = null ? leftTail : rightTail
Time - O(n)
Space - O(n) / O(log n)
Binary Tree Maximum Path Sum (Hard)
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.
maxSum = -Infinity
maxGain(root)
return maxSum
maxGain: if node = null return 0 leftGain = max(maxGain(node.left), 0) rightGain = max(maxGain(node.right, 0) sum = node.val + leftGain + rightGain maxSum = max(sum, maxSum) return node.val + max(leftGain, rightGain)
Time - O(n)
Space - O(n) / O(log n)
Binary Search Tree Iterator (Medium)
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
initialize with empty stack
leftMostInOrder(root)
leftMostInOrder:
while node != null
stack.push(node)
node = node.left
next:
nextNode = stack.pop()
if nextNode.right leftMostInOrder(nextNode.right)
return nextNode.val
hasNext:
return this.stack.length > 0
Time - O(n)
Space - O(n) / O(log n)
Binary Tree Right Side View (Medium)
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
create view push node to queue BFS iterate for queue.length / size if i === size - 1 (only push to view for last node in a level) view.push(node.val)
Time - O(n)
Space - O(n) / O(log n)
Kth Smallest Element in a BST (Medium)
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
create iterator
loop from i = 0, i < k
ans = iterator.next().value
return ans
inOrderTraversal*
if node.left yield* inOrderTraversal(node.left)
yield node.val
if node.right yield* inOrderTraversal(node.right)
Time - O(k)
Space - O(1)
Lowest Common Ancestor of a Binary Tree (Medium)
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
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).”
if root = null or root = p or root = q
return root
L = lca(root.left, p, q) R = lca(root.right, p, q)
return (L && R) ? root : (L || R)
Time - O(n)
Space - O(n) / O(log n)
Binary Tree Paths (Easy)
Given a binary tree, return all root-to-leaf paths.
paths = []
push { node: root, path: '' } to queue
BFS
shift node/path off queue
path += ->${node.val}
push left/right to queue if exist with path
if !node.left and !node.right push path to paths array
Time - O(n)
Space - O(n) / O(log n)
Closest Binary Search Tree Value (Easy)
Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
closest = root.val
while (root != null)
closest = abs(root.val - target) < abs(closest - target) ? root.val : closest
root = target < root.val ? root.left : root.right
return closest;
Time - O(n)
Space - O(1)
Serialize and Deserialize Binary Tree (Hard)
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.
serialize as dfs preorder traversal (root, left, right)
deserialize
rdeserialize(data)
if traversal[0] = null
traversal.splice(0, 1) return null
node = new Node(traversal[0]) traversal.splice(0, 1) node.left = rdeserialize(traversal) node.right = rdeserialize(traversal) return node
Time - O(n)
Space - O(n)
