Binary Tree

Binary Tree is a special data structure used for data storage purposes. A binary tree has a special condition that each node can have a maximum of two children.
A binary tree has the benefits of both an ordered array and a linked list as search is as quick as in a sorted array and insertion or deletion operation are as fast as in linked list.

Important Terms

Following are the important terms with respect to tree.

• Path − Path refers to the sequence of nodes along the edges of a tree.
• Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.
• Parent − Any node except the root node has one edge upward to a node called parent.
• Child − The node below a given node connected by its edge downward is called its child node.
• Leaf − The node which does not have any child node is called the leaf node.
• Subtree − Subtree represents the descendants of a node.
• Visiting − Visiting refers to checking the value of a node when control is on the node.
• Traversing − Traversing means passing through nodes in a specific order.
• Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
• keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

To enhance the performance of binary tree, we use special type of binary tree known as Binary Search Tree. Binary search tree mainly focuses on the search operation in binary tree. Binary search tree can be defined as follows...

Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger values in its right subtree.

Binary Search Tree Representation

Binary Search tree exhibits a special behavior. A node's left child must have a value less than its parent's value and the node's right child must have a value greater than its parent value.

Example

The following tree is a Binary Search Tree. In this tree, left subtree of every node contains nodes with smaller values and right subtree of every node contains larger values.

---

Every binary search tree is a binary tree but every binary tree need not to be binary search tree.

To Learn About Operations of BST , please visit BST operation section