Binary Tree: Introduction

What is a tree?

In computer science, a tree is a collection of nodes. Each node is a data structure consisting of a value (or possibly any data structure) and references to other nodes. The referenced nodes are called children, and the node holding the connection is the parent node. A tree is a rooted data structure, i.e., the very first node of the tree is the root, and none of the nodes reference the root node.

Tree: Rooted at Node 1

Operations on a tree

We typically perform insertion, deletion, search, and traversals on a tree:

• Insertion adds a new node in the tree.
• Deletion is the operation to delete an existing node in the tree.
• Search is to detect whether a node exists in the tree or not.
• Traversals are ways to iterate over the nodes in the tree.

Terminology

We’ll go through some of the terms used with the tree data structure. For explaining these terms, we are referring to the above tree.

• Node is a structure that contains a value or a separate data structure. Node has zero or more child nodes. For example, node 2 has two child nodes, nodes 4 and 5. Node 7 has four child nodes, nodes 10, 11, 12, and 13. Node 4, 6, 8, etc., has no child nodes.