Trees Pattern

Question 1

What exactly is a tree?

Answer 1

It’s a connected DAG with a single root where each child has only a single parent.

Alternatively you can say It’s a connected DAG with a single root where the corresponding undirected graph is also acyclic.

A tree has these node types:
Root: Only outgoing
Internal nodes: have both incoming and outgoing edges
Leaves: Only incoming

Question 2

What is a binary tree?

Answer 2

Tree that
- each node has 0-2 children

• height of binary tree is h nodes
• h can at most be n which happens when the tree is really a linked list. In which case, maybe you should use a simpler data structure like a linked list.

What is the min value of h?
It happens in a perfect/complete tree

Question 3

What are some indications that I should use a tree for a given problem?

Answer 3

• If the data is hierarchical
• The problem is recursive. In which case, we will have a recursion tree.

Question 4

How do you solve a tree problem?

Answer 4

We use recursion

We solve the problem on the left

We solve the problem on the right

We combine the result of the left and right and the root.

Traversing the tree:
DFS
- inorder or preorder traversal

PostOrder: very common for recursive solutions on trees

Question 5

How do we store the tree in code?

Answer 5

Create a node class

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

Question 6

How are BST or trees stored?

Answer 6

In node class or classes

Vectors or arrays