Tree data structure

A b tree is a generalized binary tree . How ?

A binary tree is a tree in which each node has at most 2 children. A b-tree of order m is a tree in which

• Each node has at most m children.
• Each internal node (not the root or a leaf) has at least ⌈m/2⌉ children. (⌈x⌉ means the ceiling of x, the least integer not less than x.)
• Each non-leaf node (parent and all internal nodes) has at least 2 children.
• All leaves appear on the same level.

(B tree nodes also have keys, but this is not directly part of the tree structure and does not concern us in this question.)

So some b-trees are binary trees. Every b-tree of order 2 is a binary tree. Some b-trees of higher order are binary trees if they happen not to have any nodes with more than 2 children.

b-trees of orders 5 and greater could be binary trees only if they are just a parent and two children, which are leaves. If a tree of order 5 or greater had any internal nodes, that node would be required to have at least ⌈5/2⌉ = 3 children, so it could not be a binary tree. b-trees of orders 3 and 4 could have internal nodes and still be binary trees.

The concepts of binary tree and b-tree overlap, but neither is a subset of the other in the sense that all requirements of one would satisfy the other. For the most part in programming, you are not going to mix uses of routines for binary trees and other routines for b-trees based on just how the current tree happens to be filled and arranged; on a particular set of data being managed, you would be working entirely with binary tree routines or entirely with b-tree routines.