Here are the summaries for the Tree algorithms in Leetcode's Blind 75. Check out the previous post on Strings. A tree is a subset of graph data structures where nodes are organized hierarchically. Many of these problems specifically use a binary tree in which each node can have a maximum of two child nodes, a left child node and a right child node.

Maximum Depth of Binary Tree

Given the root of a binary tree, find the max depth of the tree from the root.

Solution with O(n) time / O(n) space

Using recursion is the most natural here. Create a helper function to handle the recursion and track the depth. Call the helper function with the root node starting at a depth of 0.

For the helper function implementation, return the max of the left node’s depth and the right node’s depth. Increment the depth at each level. When the input node is null, return the current depth.

Same Tree

Given the root of two binary trees, determine if they have identical structure and values.

Solution with O(n) time / O(1) space

Recursively visit each node of both trees at the same time. If at any time, one node is not equal to the other, or one node is null while the other is not, then the trees are not the same.

Invert/Flip Binary Tree

Given the root of a binary tree, flip the nodes so that all nodes are mirrored across the root.

Solution with O(n) time / O(n) space

Set the left node to the recursive result of inverting the right node, and vice versa.

Binary Tree Maximum Path Sum

Given the root of a binary tree, return the max sum possible of a contiguous path of nodes.

Solution with O(n) time / O(n) space

Recursively visit each node, determining whether the left side or the right side path sum is larger. The overall max path sum will be the max left side sum + the max right side sum + the current node value, because that’s where the longest path could be.

You can think of it like starting from the lowest node, you can easily tell if the left side or right side is larger, then when you go up one node, you only need to consider the path with the larger sum for each side to compare.

Binary Tree Level Order Traversal

Given the root of a binary tree, return an array of arrays ordered by descending level, and each level ordered from the leftmost node to the rightmost node.

Solution with O(n) time / O(n) space

This problem can be solved more intuitively with Breadth First Search, unlike the previous problems which used Depth First Search. That means the algorithm will be looking at all nodes from each level of the tree, before moving on to the next depth.

Initialize a queue to hold the nodes from each level, starting with the root. Iterate through the levels one at a time by pulling any nodes from the queue, and pushing the nodes into the result array. Every time you pull a node from the queue, add the left child, then the right child to the queue if they exist.

As you can see, since a queue is implemented using First In First Out logic, the result array will be in the correct order if you always add nodes from the left to right.

Serialize and Deserialize Binary Tree

Given a binary tree, implement two functions to serialize into a string and deserialize it back to the tree.

Solution with O(n) time / O(n) space for each function

There are many ways to accomplish this, but one way is to serialize in DFS order (using preorder traversal).

For serialization: Recursively serialize nodes by converting the number to a string, and add a delimiter between serialized nodes (e.g. a comma). For a preorder traversal path, follow the left path down the tree until the path ends, go back up until a node contains a right child node, repeat down the left path again. Make sure to add a null value (e.g. the character “n”) when a path ends.

For deserialization: Split the serialized string using the delimiter, and add all values to a queue. Recursively pull values from the queue which will start from the root, following the same traversal path as the serialization, using the null value indicator to know when to end the recursive call.

Subtree of Another Tree

Given the root of two trees (an input tree, and an input subtree), determine if the input subtree is contained within the input tree.

Solution with O(n*m) time / O(n) space where n is the # of nodes in the input tree, and m is the # of nodes in the input subtree

Recursively check all nodes within the input tree:

1. Use this node as a root node to check for equality.
2. Does this node make up a tree that is equal to the input subtree? You can use the same method as the “Same Tree” problem, to check if the trees are equal.

Construct Binary Tree from Preorder and Inorder Traversal

Given two input arrays that describe a binary tree, one that is in preorder traversal order, and the other in inorder traversal order, return the root of the binary tree that the inputs are describing. The input arrays do not have null identifiers to denote when a path ends (that’s the main point of the question).

Solution with O(n) time / O(n) space

The important thing to realize initially is that it’s more natural to construct a tree from the top down, which is how the preorder array is ordered.

You can iterate through the preorder array (which starts at the root), adding nodes to the result tree. In order to determine whether the next node will be added on the left or the right subtree, use the inorder array. The number of values in the inorder array until the current node is the size of the left subtree.

Now that you know the size of the left subtree, recursively construct the left tree using the values from the preorder array up to the size, then construct the right subtree using the rest of the values.

Validate Binary Search Tree

Given the root of a binary tree, determine if it's a binary search tree.

Solution with O(n) time / O(n) space

Binary search trees are sorted so that everything on the left of a node is less than, and the right nodes are greater than.

Recursively check if each node’s value is between the values above it. When following left children, the previous node is the new maximum value, and vice versa for the right children.

Kth Smallest Element in a BST

Given a binary search tree, and an integer k, find the kth smallest element of the tree.

Solution with O(n) time / O(n) space

Recursively search the tree using in order traversal, returning after searching k elements.

Lowest Common Ancestor of BST

Given a binary search tree, and two input nodes, find the lowest common ancestor of the two nodes.

Solution with O(h) time / O(1) space, where h is the height of the tree

Since the tree is sorted, you can iteratively start from the root of the tree, and do a modified binary search using both input nodes. The binary search works as follows:

• If the current node is less than both input nodes, move to the right node
• If the current node is greater than both input nodes, move to the left node
• Otherwise, return the current node

Implement Trie (Prefix Tree)

Implement a Trie data structure, which is meant to efficiently store and search keys like strings.

Solution with O(n) time / O(n) space

There are 4 parts to the problem:

1. Define the data structure: Since we’re only storing strings, the data structure can be a tree where each node can have a max of 26 children (for each letter in the alphabet). You can think of it like we’re flattening a list of several separate words into one by combining letters in words that begin the same. Since there could be cases where a word is contained in another word, the data structure also needs to keep track of which nodes represent the end of a word.
2. Implement insert to add a word to the Trie: Iterate through the characters in the word, adding them to the tree always starting from the root. The characters should be added using depth-first traversal, meaning each subsequent character will have an increased depth.
3. Implement search to find a word in the Trie: Iterate through the characters in the word, traversing the tree depth-first. If all the characters were found from the search, and the last node indicates that it’s the end of a word, then return true.
4. Implement startsWith to find a word prefix in the Trie: This is the same as search except you don’t need to check if the last node represents a word.

Add and Search Word

Implement a Dictionary data structure with the ability to add and search for words.

Solution with O(w) time to add and O(n) time to search / O(n) space where w is the length of the added word, and n is the number of characters in all added words

This can be implemented as a Trie like above, where the add word function is the same as the insert function above.

One thing that’s different about the search function here is that the input could contain a wildcard character to represent one of any character. In order to handle the wildcard, you’ll need to search every child node when you encounter the wildcard, in order to see if any branch has the rest of the search term.

Word Search II

Given an m*n board and a list of string input words, return the words that are present on the board.

Solution with O(m*n*4^w) time / O(t) space, where w is the average length of a word, and t is the total characters in the words

This is similar to the first Word Search problem, but now we have multiple words to look for. You can still solve the problem using backtracking, but to optimize searching for multiple words, you can generate a Trie from the words first.