Binary Tree

The simplest (and most common) type of tree used in coding interviews is the binary tree, which is a tree with at most two children per node.

To create a binary tree, we'll first define a class for its nodes. Each node contains a value, and can have a left child node or right child node:

class Node:
   def __init__(self, value):
       self.value = value
       self.left = None
       self.right = None

# Create our simple mini tree. 
root = Node(5) 
root.left = Node(8)

Using the Node class, let's create the following binary tree:

To find a value in a tree, we use a graph traversal algorithm like depth-first search (DFS) or breadth-first search (BFS). DFS is generally easier to understand and implement, but BFS is necessary if the question revolves around levels.

Binary Search Trees

A binary search tree (BST) is a binary tree that satisfies the following properties:

1. The left subtree of a node contains only nodes with values less than the current node's value.
2. The right subtree of a node contains only nodes with values greater than the current node's value.
3. Both the left and right subtrees must also be binary search trees

Though the data structure of a BST is the same as binary tree, for a BST we need to make sure every node added is in the correct place.

The main advantage of a BST is that it allows for fast lookup, addition, and removal of items. On average, the time complexity for these operations is O(log(n)).

Non-Binary Trees

Trees that have more than two children per node are called non-binary trees. These are less common than binary trees, but they are still used in some questions.

To create a non-binary tree, we can use the same Node class as before, but instead of having two children, we use a list to store the children.

class Node:
   def __init__(self, value):
       self.value = value
       self.children = []

Let's see an example of how to create the following binary tree:

Same as a binary tree, we can find a node in a binary search tree using a traversal algorithm.

Graph Based Trees

A tree is basically a graph with more restrictions - it has no cycles and all nodes are connected. Hence we could build a tree the same way as how we build a graph.

Tries

A trie (pronounced "try") has a similar structure to a non-binary tree, but the key differences are

1. The root node always represents an empty string.
2. Its purpose is to store words in a way that makes searching for them very fast.

Here's an example trie which contains ['cat', 'car', 'cart', 'do'].

Our preferred way to design tries is storing characters in the edges while nodes store booleans.

True indicates that the node is the end of a word. (Example: We want to know that "app" is a word, but "appl" is not.)

Here's an example of a trie with: ['apple', 'app', 'apply', 'bass', 'band']

We can define each trie node to have:

• A dictionary children where each key is the next letter, and the value is the corresponding child node for that letter.
• A boolean is_word which indicates if the node is the last letter in a word.

class TrieNode:
   def __init__(self, is_word: bool):
       self.children = 
       self.is_word = is_word

Using the TrieNode class, let's create the above trie:

To find a word in a trie, we traverse it character by character. If we reach the last character of the word and its corresponding node is marked as the end of a word, the word exists in the trie.