tree data structure

node

trees store data as nodes, meaning each item in a tree is called a node
each node x has the following fields

• key(x): a key that's used to identify the node (like every data structure)
• info(x): contains the data we need to store (like every data structure)
• left(x): a pointer to the left child of x
• right(x): a pointer to the right child
• parent(x) (optional): a pointer to the parent of x

height

the height of a node x is defined as the height of subtree of said node, denoted by

balance factor

the balance factor of a node x, denoted by balance(x) or BF(x), is defined as the height of the subtree of the left child of x, denoted by minus the height of the subtree of the right child of x denoted by , in short:
see for example this tree, the balance factor of each node is written above it

height

level

root

leaf

internal node

sibling

ancestor

descendant

subtree

for some binary tree T and a node x of said tree we denote as the subtree whose root is x, and the left subtree of x is the tree whose root is the left child of x denoted by and the right subtree of x is the tree whose root is the right child of x denoted by
the height of this tree is 4

complete tree

almost complete tree

an almost complete binary tree is a binary tree from which 0 or more nodes have been deleted continuously from the right part of the last level of nodes

the nodes in the last level in an almost complete binary tree have to appear continuously from left to right

every complete tree is an almost complete tree but not every almost complete tree is a complete tree

every level contains 2 times as many nodes as the level before it, except perhaps for the last level

the height of a tree is

the number of nodes in a tree is

the number of nodes at height is

tree breadth-first search

breadth-first search or BFS for short, explores each level before moving onto the next one
extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.
broken link: attachment:Animated_BFS.gif

tree depth-first search

depth-first search or DFS for short, consists of exploring branches as far as possible before backtracking and exploring branches of other nodes
this is the algorithm we'll be using because its simpler
broken link: attachment:bfs_dfs.gif

inorder traversal

left, parent, right

  Algorithm inorder(tree)
    1. go to the left child, i.e., call inorder(left-child), print it
    2. go back to the parent, print it
    3. go to the right child, i.e., call inorder(right-child), print it

preorder traversal

parent, left, right

  Algorithm preorder(tree)
    1. visit the parent, print it
    2. go to the left child, i.e., call preorder(left-child), print it
    3. go to the right child, i.e., call preorder(right-child), print it

postorder traversal

left, right, parent

  Algorithm postorder(tree)
    1. go to the left child, i.e., call postorder(left-child), print it
    2. go to the right child, i.e., call postorder(right-child), print it
    3. visit the parent, print it

algorithms

reverse inorder

given a binary tree, write a function to reverse its inorder traversal output
this algorithm runs in O(n) time

  template <typename T>
  void reverse(BinaryTreeNode<T>* node) {
    if (node == nullptr)
      return;
    reverse(node->get_left());
    reverse(node->get_right());
    BinaryTreeNode<T>* l = node->get_left();
    node->set_left(node->get_right());
    node->set_right(l);
  }

  #include <iostream>
  <<BinarySearchTree>>
  <<BinaryTreeLatex>>
  <<reverse_inorder>>
  int main() {
    BinarySearchTree<int> t;
    t.insert(11)->insert(5)->insert(3)->insert(4)->insert(2)->insert(1)->insert(7)->insert(6)->insert(20)->insert(15);
    t.print();
    reverse(t.get_root());
    t.print();
  }

1
2
3
4
5
6
7
11
15
20
20
15
11
7
6
5
4
3
2
1