Read

Trees link

• 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. This is what a tree looks like:

Traversals

There are two categories of traversals when it comes to trees.

• Depth First
• Breadth First

Big O

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.