Trees

Trees

• Node - a node is the individual item/data that make up the data structure
• Root - The root is the first/top Node in a tree
• Left Child - The node that is positioned to the left of the root
• Right Child - The node that is positioned to the right of the root
• Edge - The edge in a tree is the link between two nodes
• Leaf - A leaf is the node that does not contain either a left child or a right child node.
• Height - The height of a tree is determined by the number of edges from the root to the bottommost node

Traversals

• There are two categories of traversals when it comes to trees.
  • Depth First
    • Depth first is a traversal that traverses the depth (height) of the tree
    • The most common way to traverse through a tree is to use recursion
  • Breadth First
    • Iterates through the tree by going through each level of the tree node by node

Binary Trees

• Trees that only contain no more than 2 children

Big O

• The Big O time of an insertion and searching in a Binary tree will always be O(n)
  • In the worst case scenario, we will have to search the whole tree for the specified value, or the place where we want to insert a new node
• The Big O space for a node insertion using breadth first will be an O(w), with “w” being largest width of the tree
• The Big O of a Binary Search Tree’s insertion and search operations is O(h), or O(height). In the worst case, we will have to search all the way down to a leaf, which will require searching through as many nodes as the tree is tall. In a balanced tree, the height of the tree is lg(n); in an unbalanced tree, the worst case height of the tree is n
• The Big O space of a Binary Search Tree (BST) search would be O(1). During the search, we are not allocating any additional space when searching for a node