Trees A tree data structure is a non-linear data structure because it does not store in a sequential manner. It is a hierarchical structure as elements in a Tree are arranged in multiple levels. Terminology Node - A Tree node is a component which may contain it’s own values, and references to other nodes Root - The root is the node at the beginning of the tree K - A number that specifies the maximum number of children any node may have in a k-ary tree. In a binary tree, k = 2. Left - A reference to one child node, in a binary tree Right - A reference to the other child node, in a binary tree Edge - The edge in a tree is the link between a parent and child node Leaf - A leaf is a node that does not have any children Height - The height of a tree is the number of edges from the root to the furthest leaf Traversals An important aspect of trees is how to traverse them. Traversing a tree allows us to search for a node, print out the contents of a tree, and much more! There are two categories of traversals when it comes to trees:
Depth First: Pre-order: root >> left >> right In-order: left >> root >> right Post-order: left >> right >> root
Pre-order: Pre-order means that the root has to be looked at first. In our case, looking at the root just means that we output its value. Binary Search Trees A Binary Search Tree (BST) is a type of tree that does have some structure attached to it. In a BST, nodes are organized in a manner where all values that are smaller than the root are placed to the left, and all values that are larger than the root are placed to the right. Big O The Big O time complexity for inserting a new node is O(n). Searching for a specific node will also be O(n). Because of the lack of organizational structure in a Binary Tree, the worst case for most operations will involve traversing the entire tree. If we assume that a tree has n nodes, then in the worst case we will have to look at n items, hence the O(n) complexity.
The Big O space complexity for a node insertion using breadth first insertion will be O(w), where w is the largest width of the tree. For example, in the above tree, w is 4.