Ticker

20/recent/ticker-posts

What is a Binary Tree

Binary Tree

What is a tree?

• A tree is recursively defined as a set of one or more nodes where one node is assigned as the root of the tree.
• All the remaining nodes can be partitioned into non-empty sets each of which is a sub-tree of the root.

Root Node: The root node A is the topmost node in the tree. If A=NULL, then it means the tree is empty.

Leaf Node: A node that has no children is called the leaf node or a terminal node of a tree.

Path:  A sequence of consecutive edges is called a path. For example from the above figure, the path from the root to the node is A->C->G->K.

Ancestor Node: AN ancestor of a node is the predecessor node on the path from the root to the node. The root node doesn't have any ancestors. In the above figure nodes A, C, G are the ancestors of node J.

Descendant Node: A descendent node is any successor node on any path from the node to a leaf node.
A leaf node doesn't have any descendants. In the above figure nodes C, G, J, K are the descendants of node A.

Level Number: Every node in the tree is assigned a level number in such a way that the root is at level 0, children of the root node are at level 1. So, every node is one level higher than its parent, and therefore all the child nodes have a level number given by the parent's level number + 1.

Degree: The degree of a node is equal to the number of children that a node has. The degree of a leaf node is 0 since it has no children.

Binary Tree:

• A binary tree is a data structure that is defined as a collection of elements called nodes.
• In a binary tree, the topmost element is called the root node.
• In a binary tree, each node has 0, 1, or at most 2 children.
• A node that has 0 children is called a leaf node or a terminal node.

• The figure shows a binary tree in which 1 is the root node and the two trees T1 and T2 are called the left and right sub-trees of the root node 1.
• T1 is said to be the left successor of the root node.
• T2 is said to be the right successor of the root node.
• A binary tree of height h has at least h nodes and at most 2h-1 nodes. This is because every level will have at least one node and can have at most 2 nodes.

Complete Binary Tree:

complete binary tree is a binary tree that is hard wired to two properties.
1. First, in a complete binary tree, every level except possibly the last level is completely filled.
2. Second, all nodes appear as far left as possible.

• In a complete binary tree Tn, there are exactly n nodes and level r of T can have at most 2^r nodes.
• Suppose in the above figure, level 0 has 2^0=1 node, level 1 has 2^1=2 nodes, level 2 has 2^2=4 nodes and level 3 has 5 nodes which are less than 2^3=8 nodes.

Full Binary Tree:

• A binary tree is said to be a full binary tree if each node in the tree has either no child or exactly two children.

• In a full binary tree, nodes having two children are called internal nodes, and nodes having no children are called external nodes.