Wallis' Blog

My Journey from Wall Street To & Through Flatiron School

Binary Search Trees

What are “binary search nodes”?

Binary search nodes are the components of a binary search tree (“BST”). What is a BST? Going with the old adage that a picture is worth a thousand words, I thought this image from Wikipedia was very helpful:

binary search tree

Any circle in this drawing is a “node”. There are a couple things you’ll notice about a BST:

  • Pick any node in the tree, and you will see that:
    • All nodes in the chosen node’s left subtree are LESS than the chosen node
    • All nodes in the chosen node’s right subtree are GREATER than the chosen node
    • Each subtree is itself a BST
    • Each node is unique

    There are a few terms to konw when talking about BSTs:

    • Root - the base of the tree, i.e. it has no parents (in the picture above, 8)
    • Leaves - the nodes that have no children (in the picture above, 1, 4, 7 & 13)
    • Size - total # of nodes (in the picture above, size = 9)
    • Depth - the depth of a particular node is # of steps between the root node & that particular node (in the picture above, the depth of node 6 is “2”). Note that the depth of the root node is zero
    • Height - the height of a tree is the depth of the deepest node, aka “the depth of the tree”

    The maximum number of nodes in a tree is equal of 2^(h+1) - 1, where h = height of the tree

    This highly structured format makes BSTs an efficient way of searching or sorting data.

    Other names for BSTs:

    • Ordered binary tree
    • Sorted binary tree