Trees are a subset of graphs, a non-linear data structure, that provides an efficient way for searching and sorting. They are a collection of nodes and are a way to store information hierarchically.
Similar to regular trees, they have parent and child nodes that are connected in a hierarchical fashion.
A binary tree is a tree data structure in which each node has at most two child nodes, known as the left child and the right child. The topmost node in the tree is known as the root, and each child node can have its own subtrees, which are also binary trees.
In a binary tree, each node has a unique value, and the values in the left subtree of a node are less than the value of the node, while the values in the right subtree are greater than the value of the node. This ordering property makes binary trees useful for searching and sorting data.
In this example, the node labeled 1 is the root node, while 8,9,10,11,13, and 14 are the called leaves, and the rest of the nodes are called internal nodes.
Some terminology:
Full tree - tree where every node have two children except the leaves
Complete tree - every node has at least two children except for the bottom level, and they have to be filled in as far left as possible
Degenerate tree - every node only has one child node
Perfect tree - every internal node has two children and all leaves are on the same level
Balanced tree - height of the left and right subtree of any node differ by not more than 1
For traversal of a binary tree, there are three different ways:
preorder: [1,2,4,6,3,5,7,8,9]
inorder: [6,4,2,1,3,7,5,9,8]
postorder: [6,4,2,7,9,8,5,3,1]
Breadth first traversal, an alternate to depth first, is an algorithm that searches each level, left to right.
Algorithm Steps
