Binary Search Tree
A foundational data structure in computer science is the binary search tree. But what is it? Lets break it down!
What defines a Tree?
- A non-linear data structure
- Made up of nodes containing data
- Nodes are connected by edges in pairs
What are some important terms to know?
- In each connected pair of nodes the node 'on top' is the parent and one 'below' it is the child
- Nodes with the same parent are siblings
- Each tree with data will have one top node with no parent, called the root node
- Nodes without children are leaf nodes or external nodes
- Nodes with children are internal nodes
- A subtree is a smaller tree within the tree structure; the subtree's root is a non-root node from the larger tree
- Each tree has levels, with the root node being on level 0, its direct children being on level 1, and so on
- The depth of a node is the level that it is on, or the number of edges on the path from the node to the root
- The height of a node is the number of edges from that node to the deepest level in the tree
- The height of a tree is the height of its root node
What makes a Tree a Binary Tree?
Every node in the tree has at most two children. It's that simple! One of them is called the 'left child' and the other the 'right child', if they exist.
What makes a Binary Tree a Binary Search Tree?
A binary tree becomes a binary search tree when the data contained in all the nodes of the left child's subtree all have a lower value than the data contained in its parent node. If your binary search tree is storing numbers, that means all left children must store a lower number than their parent, as must all of the children of that left child. Additionally, any right childrens' subtrees must contain larger values than their parent's. For example if your binary search tree contains String data, the right child's data must come before its parent's in the alphabet. If a child and parent's data have equal value, then it is up to the programmer if the child should go to the left or the right slot.
Want more info? Check here!