Introduction to the Binary Tree

About Binary Trees

Why use a binary tree?

  • Store information that naturally forms a hierarchy like the file system on a computer, data on relationships, or many other things.
  • Trees provide moderate speed of searching (quicker than a linked list and slower than arrays)
  • Trees provide moderate insertion/deletion (quicker than Arrays and slower than unordered linked lists).
  • Unlike Arrays, trees don’t have an upper limit on number of nodes as nodes are linked using pointers (the lines you see connecting nodes).

A further look into the structure

Binary Search Tree

Traversing through a binary search tree

  • To insert the 17, we would start at the root 30. 17 is less than 30 so we are going to go to the left child of 30.
  • We are now standing on 20 and 17 is less than 20. Like before want to go to the left.
  • We have reached 10 and for once 17 is greater than 10 so we will move to the right child.
  • Finally we have reached 15 which is a leaf node (has no children). 17 is larger than 15 so we want to insert it as the right child of 15 and that is where it will stay.

Types of traversals

Final thoughts

--

--

Student at The Flatiron School in Washington DC

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store