Binary Tree

• Data structure in which each node has at most two children, referred to as the left child and the right child.
• The nodes are arranged in a hierarchical structure, with a root node at the top and the leaves at the bottom
• Traversing a tree (Example uses above tree)
  • Preorder: Root → Left → Right (1 → 2 → 4 →8 → 9 → 5 → 10 → 3 → 6 → 7)
  • Inorder: Left → Root → Right (8 → 4 → 9 → 2 → 10 → 5 → 1 → 6 → 7 → 3)
  • Postorder: Left → Right → Root (8 → 9 → 4 → 10 → 5 → 2 → 6 → 7 → 3 → 1)

Binary Search Tree

A binary search tree (BST) is a binary tree in which each node has a value greater than all the values in its left subtree and less than all the values in its right subtree.
Advantage: Fast Search, insertion and deletion

Traversing in Binary Search Tree

• Inorder
  • Left → Root → Right
  • 1 → 3 → 2 → 4 → 5 → 6 → 8 → 9 → 10 → 11
• Preorder
  • Root → Left → Right
  • 8 → 4 → 3 → 1 → 2 → 6 → 5 → 10 → 9 → 11
• Post Order
  • Left → Right → Root
  • 1 → 2 → 3 → 5 → 6 → 4 → 9 → 11 → 10 → 8
• Searching for a particular data
  • Start at the root node and keep comparing
  • If search value smaller than current node, go left
  • If search value bigger than current node, go right
• Finding Minimum Value
  • Go to the leftmost child (One with no left-child)
• Finding Maximum Value
  • Go to the rightmost child (One with no right-child)
• Adding/Inserting a Value
  • Start at the root and compare the value you want to insert.
  • Move left or right:
    • If the value is smaller than the current node, go to the left child.
    • If the value is larger than the current node, go to the right child.
  • Find the correct position:
    • If the tree is empty, insert the value at the root.
    • Otherwise, traverse until you find a leaf node (a node with no child in the required direction).
  • Insert the new node:
    • If the new value is smaller than the parent, make it the left child.
    • If the new value is larger than the parent, make it the right child.
    • For duplicate values, it is safest to avoid insertion, or optionally, insert as the right child of the duplicate

Code for Binary Tree

No output yet.