Skip to content

Latest commit

 

History

History
62 lines (35 loc) · 2.91 KB

class15.md

File metadata and controls

62 lines (35 loc) · 2.91 KB
Raw

Trees

Common Terminology

  1. Node - A node is the individual item/data that makes up the data structure
  2. Root - The root is the first/top Node in the tree
  3. Left Child - The node that is positioned to the left of a root or node
  4. Right Child - The node that is positioned to the right of a root or node
  5. Edge - The edge in a tree is the link between a parent and child node
  6. Leaf - A leaf is a node that does not contain any children
  7. Height - The height of a tree is determined by the number of edges from the root to the bottommost node

Traversals

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:

1.Depth First 2.Breadth First

Depth First

Depth first traversal is where we prioritize going through the depth (height) of the tree first. There are multiple ways to carry out depth first traversal, and each method changes the order in which we search/print the root. Here are three methods for depth first traversal:

Pre-order: root >> left >> right

In-order: left >> root >> right

Post-order: left >> right >> root

The most common way to traverse through a tree is to use recursion. With these traversals, we rely on the call stack to navigate back up the tree when we have reached the end of a sub-path.

Breadth First

Breadth first traversal iterates through the tree by going through each level of the tree node-by-node.

Binary Trees

There is no specific sorting order for a binary tree. Nodes can be added into a binary tree wherever space allows. Here is what a binary tree looks like:

Adding a node

Because there are no structural rules for where nodes are “supposed to go” in a binary tree, it really doesn’t matter where a new node gets placed.

One strategy for adding a new node to a binary tree is to fill all “child” spots from the top down. To do so, we would leverage the use of breadth first traversal. During the traversal, we find the first node that does not have 2 child nodes, and insert the new node as a child. We fill the child slots from left to right.

In the event you would like to have a node placed in a specific location, you need to reference both the new node to create, and the parent node upon which the child is attached to.

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.

Searching a BST Searching a BST can be done quickly, because all you do is compare the node you are searching for against the root of the tree or sub-tree. If the value is smaller, you only traverse the left side. If the value is larger, you only traverse the right side.