Binary Tree

Introduction to binary trees

The main reason we’re studying data structures is to organize data most efficiently. A binary tree is a specialized representation of data structure. A binary tree is used for data storage purposes. A tree is represented by nodes that are connected by edges or pointers.

A binary tree has a unique condition, making it very special among other data storage mechanisms. A node of a binary tree can have a maximum of two children. When it has one or two children, we call it a subtree. Each node of a subtree can have more subtrees.

When a tree node or subtree node doesn’t have children, it’s called a leaf node.

While traversing a tree, we always take the leaf node as our ending point or base case for recursion. We can search a binary tree as an ordered array. We can also insert and delete data in any binary tree like we do in a linked list.

A binary tree’s sequence of nodes is known as a path. This path starts at the top of the node, referred to as the root. There’s always only one root and one path to the other node. It has no duplicate path. The nodes placed below are children; these children nodes always have nodes above them, known as parent nodes.

If we consider a root node as the parent node, then this node is on level one. The node just below is placed at level two.

Tree traversal algorithms

Trees can be traversed in a few different ways: preorder, postorder, and inorder. There are different algorithms for each kind of tree traversal. In this lesson, we’ll briefly examine tree traversal algorithms.

As we learned in the previous lesson, in some cases, recursions are essential. Most tree-based algorithms can be easily implemented using recursion because a binary tree is a recursive data structure. Although learning to solve the same problems with recursion is wise, we can also solve tree-based algorithms using iteration.