Trees

Trees are undirected graphs whieh satisfy any of:

Acyclic connected graph.
Connected graph with N nodes and N-1 edges.
For any two vertices, there is only one path between those two.

The term ‘rooted tree’ means that we have the top most node of the tree or the ‘root node’. But it is important to know that if you have any node, then you could find the root node.

A child node is a node that extends from another node and tthe parent node is the inverse. (So the root node has no parent, sometimes people say the parent of the root is itself, for example in a filesystem)

A leaf node is a node with no children.

A subtree is a tree entirely contained within another (they are usually denoted with triangles) Note: Subtrees may consist of a single node.

Binary Tree

Tree for which every node has at most two child nodes.

Binary Search Tree

Its a binary tree that satisfies the BST invariant: left subtree has smaller elements and right subtree has larger elements.

Whan are BTs used

BSTs
- Implementation of some map and set abstract data types.
- Red Black Trees.
- AVL Trees.
- Splay Trees.
Binary heaps.
Syntax trees.
Treap (probabilistic data structure that uses a randomized BST)

Complexity of BSTs

Op	Average	Worst
Insert	O(log(n))	O(n)
Delete	O(log(n))	O(n)
Remove	O(log(n))	O(n)
Search	O(log(n))	O(n)

Operations in a BST

Add an element

Compare an the element’s value to the value stored in the current node we’re considering to decide one of the following:

Recurse left subtree (<)
Recurse right subtree (>)
Handle a duplicate (=)
Create new node (found null leaf)

Remove an element

Find the element we want to remove.
1. Null node → value does not exist.
2. Comparator is 0 → found the element.
3. Comparator is less than 0 → might be in the left subtree.
4. Comparator is greater than 0 → might be in the right subtree.
Replace the node we want to remove with its successor.
- Node is a leaf: Remove it without a side effect.
- Node has a right subtree but no left subtree: Succesor will be the root node of the left subtree.
- Node has a left subtree but no right subtree: Succesor will be the root node of the right subtree.
- Node has both a left and right subtree: The succesor can be (1) the largest value in the left subtree OR (2) the smallest value in the right subtree.

After the initial deletion you might need to do anothere deletion (for example, if you remove the root node, you will then have to remove the element that replaced the root node from lower in the tree) however, that deletion will always have either ONE or NO subtrees. (so it’s easier)

Traversals

Preorder

“Prints before the recursive calls” Print the value of the current node then traverse the left subtree followed by the right subtree.

preorder(node):
  if node == null: return
  print(node.value)
  preorder(node.left)
  preorder(node.right)

Result: 11, 6, 3, 1, 5, 8, 15, 13, 12, 14, 17, 19

Inorder

“Prints between the recursive calls” Traverse the left subtree, print the value of the node and continue traversing the right subtree. Result is in order for a BST.

inorder(node):
  if node == null: return
  inorder(node.left)
  print(node.value)
  inorder(node.right)

Result: 1, 3, 5, 6, 8, 11, 12, 13, 14, 15, 17, 19

Postorder

“Prints after the recursive calls”

postorder(node):
  if node == null: return
  postorder(node.left)
  posrtorder(node.right)
  print(node.value)

Result: 1, 5, 3, 8, 6, 12, 14, 13, 19, 17, 15, 11

Level Order

Print the nodes as they appear one layer at a time.

To do this we need to do a Breadth First Search (BFS) from the root node down to the leaf nodes.

Result: 11, 6, 15, 3, 8, 13, 17, 1, 5, 12, 14, 19

juanr.co

Explorer

Binary Trees and Binary Search Trees