1.8. Binary Tree Basics

A binary tree is just a tree with a root in which every node has either 1, 2 or 3 children. The heap poses a very special kind of binary tree, which we fill up top to bottom left to right, but in general, a binary tree has no constraint. So, we have values at each node, and we will assume that not only do we have a way to go from the parent to the child, but we also have a way to go from the child to the parent. Every node is assumed to have links to its parent, left child, and right child.

A binary tree is a data structure that consists of nodes, each of which can have at most two children, called the left child and the right child. Unlike heaps, binary trees do not follow a specific structure regarding how nodes are arranged, apart from the binary condition. This means that while a binary tree has no restrictions on how it is filled (it can be unbalanced), it allows easy traversal and manipulation. Every node maintains a connection to its parent and its children, which makes navigating the tree straightforward.

Imagine a family tree where each person can have two parents (biological and adoptive). You can navigate and find relatives both ways—up to your grandparents or down to your children, just like in a binary tree where you can navigate from a node to its parent or to its children.

In terms of terminology, the root is the topmost node, it has no parent. A leaf is any node which has no children, and at any given point, if you look at a node, then it is a parent of its left child and right child.

In a binary tree, key terms help describe the nodes and their relationships. The root is the starting point of the tree and has no parent. Leaves are nodes that do not have any children, meaning they are at the end of a branch in the tree. Each internal node (any node that is not a leaf) has connections to its left and right children, which are essential for navigating and manipulating the tree structure.

Think of a tree in your backyard. The trunk of the tree represents the root, while the branches represent nodes. The leaves at the end of the branches are like leaf nodes. Just as you can see which branches lead to which leaves, you can navigate a binary tree from parent to child linked relationships.

In a binary search tree (BST), a binary tree is further constrained by how values are arranged. For each node with a value v, all nodes below v (in the left subtree) contain values smaller than v, and all nodes in the right subtree contain values greater than v. Typically, there are no duplicate values.

A binary search tree has a special property that makes searching for values efficient. In a BST, every left child must have a value less than its parent node, and every right child must have a value greater. This systematic arrangement allows for optimized searching, as you can decide which subtree to explore next based on the value you are looking for, leading to efficient operations like insertions, deletions, and lookups.

Consider a library where books are organized alphabetically. The books to the left of a particular letter (like 'M') are all books starting with letters A through L, and those to the right are M through Z. If you're searching for a book, you can quickly decide which section to head to based on the first letter, just like how a binary search tree allows for quick searches.

The first thing we can do with a binary search tree is to list its values in sorted order. This is called an in-order traversal. In an in-order traversal, we walk through the tree recursively: first through the left subtree, then the current node, and then the right subtree.

In-order traversal is a method to access all the nodes in a binary search tree in a sequence that results in sorted output. By visiting the left child before the parent and the right child afterward, we ensure that the smaller values are printed first. This method of traversal leverages the properties of the binary search tree to produce values in a sorted manner efficiently.

Imagine you’re organizing a group of friends by age. You visit the youngest friend first, then check yourself as the next eldest, and finally, you visit the oldest friends afterward. This methodical approach ensures that you can announce their ages in order, similar to how in-order traversal lists values from a binary search tree.

Searching for a value in a binary search tree is similar to binary search. If the tree is empty, we say that the value is not there. If the current node has the value we are looking for, we found it and return true. If the value is smaller than the current value, we recursively search in the left subtree; if it is greater, we search in the right subtree.

The process of searching a value in a binary search tree is efficient due to the arrangement of values. By comparing the target value with the current node’s value, we can determine whether to explore the left or right subtree. This method reduces the number of comparisons necessary to find a value, achieving a logarithmic time complexity under balanced conditions.

Imagine you're looking for a specific book in a well-organized library. Instead of checking every shelf, you first look at the section that covers the alphabet before your book; if it’s not there, you quickly skip to the next section, efficiently narrowing down your search. This mirrors how a binary search tree allows you to find values rapidly based on their ordered structure.

--