A complete binary tree by my understanding can have incomplete nodes in the last level of the tree. What is a full binary tree? What is the difference?

2

3 Answers

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.

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.

Here's the source for these descriptions and a picture for reference:

1

A complete binary tree is the most balanced tree for any no. of nodes. A full binary tree is what the most balanced tree would be if you have exactly (2^n) -1 nodes. Also, by convention, the empty space in a complete binary tree is kept at the right of the tree. edit: by most balanced, i mean the one with least depth for given no. of nodes.

Perfect Binary Tree: 1. All the Internal nodes must having two children. 2. All the leaf nodes are at the same level.

Example : A1 B1 B2 C1 C2 C3 C4

Complete Binary Tree:All the levels are completely filled except possibly the last level

Example :

 A1 B1 B2 C1 C2 C3 C4
D1 D2 D3 

Full Binary Tree:Simply Every node has 0 or 2 children.

Example :

 A1 B1 B2 C1 C2 C3 C4
D1 D2 

Do update if the answer is aggree

1

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy