Code 401: Class 15 - Trees

---

Read: Trees

• Node individual item that makes up the data structure
• Root first/top node in the tree
• Left Child node positioned to the left of a root or node
• Right Child node positioned to the right of a root or node
• Edge the link between a parent and a child
• Leaf a node that does not contain any children

• Height determined by the number of edges from the root to the bottommost node

• Depth First Traversal prioritized going through th height of the tree first
  • Pre-order root»left»right
  • In-order left»root»right
  • Post-order left»right»root

• Breadth First Traversal prioritizes going through each layer of the tree

• Binary Trees can have any number of nodes, but only two children of each node

• Big O
  • Time Complexity = O(n) because worst case scenario is that it will require checking every node
  • Space Complexity = O(w) w = the largest width of the tree

• In a perfect binary tree (one where every non-leaf node has two children) the max width = 2^(h-1) h = height of the tree. Height can be calculated as log n where n = number of nodes.

• Binary Search Tree (BSN) Structured tree in which all values smaller than the root are placed to on the left child, all larger values placed to the right
  • Searching can be done quickly because only have to compare the target value with the root of the tree or sub tree. If the target is smaller only have to search the left side, if larger only the right, this is true for each comparison.
  • Search using a while loop end when a leaf or target value is found
  • Big O
    • Time complexity = O(h) h = height
    • Space complexity = O(1) no additional space is allocated during the search

---

Return to reading-notes Deployed Site

Return to reading-notes Mark Down