Trees

Problems

#	Problem	Difficulty	Hint	Tags
226	Invert Binary Tree - LeetCode	Easy	Hint Use DFS and swap the left and right children of each node.	#tree #depthfirstsearch #breathfirstsearch #binarytree
543	Diameter of Binary Tree - LeetCode	Easy	Hint Calculate the height of the left and right subtrees and add them together to get the diameter. Update the result accordingly.	#tree #depthfirstsearch
100	Same Tree - LeetCode	Easy	Hint Run DFS, checking if the nodes are the same at each iteration.	#linkedlist #twopointers
235	Lowest Common Ancestor of a Binary Search Tree - LeetCode	Medium	Hint The LCA of a BST is when the root is greater than one of the values and less than one of the other values.	#tree #depthfirstsearch #breathfirstsearch #binarytree
102	Binary Tree Level Order Traversal - LeetCode	Medium	Hint Binary tree level order traversal is easily done using BFS. Think about the implementation details.	#tree #breathfirstsearch #binarytree
98	Validate Binary Search Tree - LeetCode	Medium	Hint Keep track of the interval that each node must be in.	#tree #binarytree #breathfirstsearch #depthfirstsearch
105	Construct Binary Tree from Preorder and Inorder Traversal - LeetCode	Medium	Hint Inorder cuts the tree in half, preorder the first node is always the root. How can we use this information to construct the tree?	#array #hashtable #divideandconquer #tree #binarytree
230	Kth Smallest Element in a BST - LeetCode	Medium	Hint An inorder travel will return the kth smallest elements in order.	#tree #binarytree #depthfirstsearch
124	Binary Tree Maximum Path Sum - LeetCode	Hard	Hint Same thing as finding the diameter of the tree except we ignore negative values.	#tree #depthfirstsearch #binarytree

Trees represent a tree-like structure with a set of connected nodes. There is a root node which can have as many children but each child can only have one parent node. Trees are acyclic and undirected, meaning they have no cycles or loops.

Common Terms

Neighbour - Parent or child of a node (connected by only one edge)
Ancestor - A node that is reachable by going up its parent nodes
Descendant - A node that is in the subtree of a node
Degree - Number of child nodes of one node
Degree of a tree - Maximum degree of nodes in the tree
Distance - Number of edges along the shortest path between two nodes
Level/Depth - Number of edges along a unique path between a node and the root node
Width - Number of nodes in a level or certain depth
Diameter - length of the longest path between any two nodes in a tree

Binary Trees

Binary trees have a maximum of two child nodes.

Terms

A complete binary tree is where every node has two child nodes except for the last level.

A balanced binary tree is where the height of the left and right subtrees differ by no more than 1.

Traversals

Depth First Search:

In-order: Left -> Root -> Right
Pre-order: Root -> Left -> Right
Post-order: Right -> Left -> Root

Binary Search Trees

In order traversal will give you the elements in order. All the values in the left subtree of the current node is less than the value of the current node. All the values in the right subtree are greater than the current node.

Techniques

Recursion

When you notice that solving a subtree solves the problem, use recursion. Always remember the base case. Sometimes, we might need to return two vaues.

Traversing by level

If this comes up, use breadth first search (queue).