A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a treedata structure in which each node has at most two children (referred to as the left child and the right child).

**Binary tree**

A simple
binary tree of size 9 and height 3, with a root node whose value is 2. The
above tree is
unbalanced and not sorted. In computer science, a **binary tree** is a treedata structure in which each node has at most
two children (referred to as the left child and the right child). In a binary
tree, the degree of each node can be at most two. Binary trees are used to
implement binary search trees and binary heaps, and are used for efficient
searching and sorting. A binary tree is a special case of a Kary tree, where k
is 2.

**Types of binary trees**

Tree
rotations are very common internal operations on self-balancing binary trees.

A **rooted binary tree** is a tree with a
root node in which every node has at most two children.

• A **full binary tree** (sometimes **2-tree** or **strictly binary tree**) is a tree in which every node other than the
leaves has two children. A full tree is sometimes ambiguously defined as a
perfect tree. Physicists define a binary tree to mean a full binary tree.[1]

• A **proper
binary tree** is an ordered tree in which each internal node has exactly two
children.

• A **perfect binary tree** is a full binary
tree in which all leaves have the same depth or same level, and in which every
parent has two children.[2] (This is ambiguously also called a complete binary
tree (see next).) An example of a perfect binary tree is the ancestry chart of
a person to a given depth, as each person has exactly two biological parents (one
mother and one father); note that this reverses the usual parent/child tree
convention, and these trees go in the opposite direction from usual (root at
bottom).

• A **complete binary tree** is a binary tree
in which every level, except possibly the last, is completely filled, and all
nodes are as far left as possible.[3] A tree is called an almost complete
binary tree or nearly complete binary tree if the exception holds, i.e. the
last level is not completely filled. This type of tree is used as a specialized
data structure called a heap.

• An **infinite complete binary tree** is a tree
with a countably infinite number of levels, in which every node has two
children, so that there are 2d nodes at level d. The set of all nodes is
countably infinite, but the set of all infinite paths from the root is
uncountable, having the cardinality of the continuum. These paths correspond by
an order-preserving bijection to the points of the Cantor set, or (using the
example of a Stern–Brocot tree) to the set of positive irrational numbers.

• A **balanced binary tree** is commonly
defined as a binary tree in which the depth of the left and right subtrees of
every node differ by 1 or less,[4] although in general it is a binary tree
where no leaf is much farther away from the root than any other leaf.
(Different balancing schemes allow different definitions of "much
farther".[5]) Binary trees that are balanced according to this definition
have a predictable depth (how many nodes are traversed from the root to a leaf,
counting the root as node 0 and subsequent nodes as 1, 2, ...,n). This depth
(also called the height) is equal to the integer part of log2(n), where n is
the number of nodes on the balanced tree. For example, for a balanced tree with
only 1 node, log2(1) = 0, so the depth of the tree is 0. For a balanced tree
with 100 nodes, log2(100) = 6.64, so it has a depth of 6.

• A **degenerate** (or **pathological**) **tree** is a
tree where each parent node has only one associated child node. This means that
performance-wise, the tree will behave like a linked list data structure.

Note that
this terminology often varies in the literature, especially with respect to the
meaning of "complete" and "full".

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Non-Linear Data Structures : Binary tree and Types of binary trees |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.