Trees and Graphs

A node is an abstract data type with two things.

First, a node stores data.
Second, a node stores pointers to other nodes.

A graph is any collection of nodes and their pointers to other nodes.

The nodes of a graph are also called vertices, and the pointers that connect them are called edges.

The start of a linked list was called the head. The start of a binary tree is called the root.

In a linked list, a node’s pointer pointed to the next node. In a tree, a node has pointers to its children. If a node A is pointing to a node B, then B is a child of A, and A is the parent of B. The root is the only node that has no parent. In a tree, a node cannot have more than one parent.

In a binary tree, all nodes have a maximum of two children. These children are referred to as the left child and the right child.

The root node is the node at the “top” of the tree. Every node in the tree is accessible starting from the root node.

If a node has no children, it is called a leaf node. The leaf nodes are the leaves of the tree.

The depth of a node is how far it is from the root node. The root has a depth of 0. Every child has a depth of parentsDepth + 1, so the root’s children have a depth of 1, their children have a depth of 2, and so on.

A subtree of a tree is a node and all its descendants.

Trees are recursive. You can take any given node and treat it as its own tree, which allows you to solve problems in a recursive manner.

When traversing linked lists, we usually do it iteratively. With binary trees, we usually do it recursively.

There are two main types of tree traversals. The first is called depth-first search (DFS). For binary trees specifically, there are 3 ways to perform DFS - preorder, inorder, and postorder. The other main type of traversal is called breadth-first search (BFS).

DFS

In a DFS, we prioritize depth by traversing as far down the tree as possible in one direction (until reaching a leaf node) before considering the other direction.

Because we need to backtrack up the tree after reaching the end of a branch, DFS is typically implemented using recursion, although it is also sometimes done iteratively using a stack.

Each function call solves and returns the answer to the original problem as if the subtree rooted at the current node was the input.

In preorder traversal, logic is done on the current node before moving to the children.

For inorder traversal, we first recursively call the left child, then perform logic (print in this case) on the current node, and then recursively call the right child. This means no logic will be done until we reach a node without a left child since calling on the left child takes priority over performing logic.

In postorder traversal, we recursively call on the children first and then perform logic on the current node. This means no logic will be done until we reach a leaf node since calling on the children takes priority over performing logic. In a postorder traversal, the root is the last node where logic is done.

The name of each traversal is describing when the current node’s logic is performed.

Pre -> before children
In -> in the middle of children
Post -> after children

Postorder and inorder are more complicated to implement than preorder (which is very easy). For most problems, the type of DFS doesn’t matter.

BFS

In BFS, we traverse all nodes at a given depth before moving on to the next depth.

While DFS was implemented using a stack (recursion uses a stack under the hood), BFS is implemented iteratively with a queue.

You can implement BFS with recursion, but it wouldn’t make sense as it’s a lot more difficult without any benefit.

In many problems, it doesn’t matter if you choose preorder, inorder, or postorder DFS, the important thing is that you just visit all nodes. If you have a problem like this, then it doesn’t matter if you use BFS either, because every “visit” to a node will store sufficient information irrespective of visit order.

Because of this, in terms of binary tree algorithm problems, it is very rare to find a problem that using DFS is “better” than using BFS. However, implementing DFS is usually quicker because it requires less code, and is easier to implement if using recursion, so for problems where BFS/DFS doesn’t matter, most people end up using DFS.

There are quite a few problems where using BFS makes way more sense algorithmically than using DFS. Usually, this applies to any problem where we want to handle the nodes according to their level.

The main disadvantage of BFS is that if the node you’re searching for is near the bottom, then you will waste a lot of time searching through all the levels to reach the bottom.

If you had a huge tree, and you were looking for a value that is stored in the root’s right child. If you do DFS prioritizing left before right, then you will search the entire left subtree

With an efficient queue, the dequeue and enqueue operations are $O(1)$, which means that the time complexity of BFS is the same as DFS. Again, the main idea is that we visit each node only once, so the time complexity is $O(n⋅k)$ where $n$ is the total number of nodes, and $k$ is the amount of work we do at each node, usually $O(1)$.

Binary Search Tree

A binary search tree (BST) is a type of binary tree. A BST has the following property: For each node, all values in its left subtree are less than the value in the node, and all values in its right subtree are greater than the value in the node.