Trees - andrewkyllo-401-advanced-javascript/seattle-javascript-401d34 GitHub Wiki

Common Terminology

• Node - A node is the individual item/data that makes up the data structure
• Root - The root is the first/top Node in the tree
• Left Child - The node that is positioned to the right of a root or node
• Right Chile - The node that is positioned to the right of a root or node
• Edge - The edge in a tree is the link between a parent and child node
• Leaf - A leaf is a node that does not contain any children
• Height - The height of a tree is determined by the number of edges from the root to the bottom-most node

Traversals

Depth First

• Going through the depth (height) of the tree first
  • Pre-order root >> left >> right
  • In-order left >> root >> right
  • Post-order left >> right >> root

Breadth First

• Iterates through the tree by going through each level of the tree node-by-node

Binary Trees

• Have only 2 children per node.

Adding a node

• Find the first node that doesnt have two child nodes to fill child spots from top down.

Big O

• Inserting a new node and searching for a node is O(n) of time
• The space complexity for a node insertion is O(w) where w is the largest width of the tree

Binary Search Trees

• Nodes are organized in a manner where all values that are smaller than the root are placed to the left and all larger values are placed to the right.

Big O

• The Big O time complexity is O(h) and time complexity is O(1)