Data Structures for Coding Interviews in Java/

...

/

Types of Trees

Types of Trees

In this chapter, we are going to discuss N-ary and Balanced Trees.

We'll cover the following...

Introduction

Trees being advanced data structures, offer a wide variety of types to provide an efficient solution, specific to a particular use. Trees are extensively used in Artificial Intelligence and complex algorithms to provide an efficient storage mechanism for problem-solving. Based on the structure, height, and other features like time/space complexity, there are different types of trees.

The most commonly used types are listed below:

  • N-ary Tree
  • Balanced Tree
  • Binary Tree
  • BinarySearchTree
  • AVL Tree
  • Red-Black Tree
  • 2-3 Tree

Let’s take a look at N-ary and Balanced Trees in this lesson and the other types later in the chapter.

N-ary Tree

In N-ary trees, each node can have child nodes anywhere from 0 to N. So if it’s a 2-ary tree, commonly known as a Binary Tree, it can have a max. of 0-2 child nodes. Can you guess the value of N in the figure shown below?

Error in Graphviz code!!syntax error in line 1 near 'null'
%0 1 1 2 2 1->2 3 3 1->3 4 4 1->4 6 6 1->6 null 5 3->null 7 7 3->7 8 8 4->8
N-Ary Tree

Balanced Tree

A balanced tree is a tree in which almost all leaf nodes are present at the same level. This condition is generally applied to all sub-trees. This means that all the sub-trees in a tree need to be balanced, no matter how many there are. Mathematically, it can be expressed as:

...