O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Searching

Here again is a binary tree:

images/chapter13/binary_trees_Part4.png

The algorithm for searching within a binary tree begins at the root node:

  1. Inspect the value at the node.
  2. If we’ve found the value we’re looking for, great!
  3. If the value we’re looking for is less than the current node, search for it in its left subtree.
  4. If the value we’re looking for is greater than the current node, search for it in its right subtree.

Here’s a simple, recursive implementation for this search in Python:

 def​ ​search​(value, node):
 # Base case: If the node is nonexistent
 # or we've found the value we're looking for:
 if​ node ​is​ None ​or​ node.value == value:
 return​ node
 
 

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required