Insertion

To discover the algorithm for inserting a new value into a binary tree, let’s work with an example. Say that we want to insert the number 45 into the previous tree.

The first thing we’d have to do is find the correct node to attach the 45 to. To begin our search, we start at the root:

images/chapter13/binary_trees_Part6.png

Since 45 is less than 50, we drill down to the left child:

images/chapter13/binary_trees_Part10.png

Since 45 is greater than 25, we must inspect the right child:

images/chapter13/binary_trees_Part11.png

45 is greater than 33, so we check ...

Get A Common-Sense Guide to Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.