Introduction

abstract data type that represents a hierarchical structure with a set of connected nodes
each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent
a tree is an undirected and connected acyclic graph ⇒ there are no cycles or loops
each node can be like the root node of its own subtree, making recursion a useful technique for tree traversal
for the purpose of interviews, you will usually be asked on binary trees as opposed to ternary (3 children) or N-ary (N children) trees

Elements

node in the tree that has no incoming edges
it has no parent, although it may be useful to assign the parent of the root node to be itself e.g. filesystem tree
a rooted tree
- we have a reference to the root node of our tree
- it does not always matter which node is selected to be the root node because any node can root the tree

a key
additional information, called “payload”, usual in applications that make use of trees
every node (except the root) is connected by exactly one incoming edge from another node
each node may have several outgoing edges