Binary(search) Tree

Representation, Code implementation on Creating BTree, Deleting, and Traversing Nodes

“Hi, There”, we learned about Tree data structure fundamentals and various kinds of trees(BTrees, BSTrees, Skewed Trees, Full or Complete BTrees), the relationship between tree nodes and height in our previous two articles:

Tree Data structure— Part-I

Tree Data structure — Part-2

This article will explore how to represent the Binary Trees with Array and Doubly Linked List. Also will learn how to Construct and traverse the Binary trees with Java programs.

Array Representation:

We know Arrays will store the elements in the contiguous memory blocks. Each block can be accessed with indexes. So we will take the nodes of trees from each level and will fill them in the array from left to right i.e index ‘0’ to towards right or end of the array(index starts from 1 in some programming languages)

Ex:

so if you see how the nodes were arranged level-wise in the array from left to right.

(Table to formulate and find an index of any left or right child)

To find an index of any element from the root, we can use the formulas,

The left child of root ‘B’ is ‘D’:

(2 * 1) +1 (B is at index 1) => 3 (D)

The left child of root ‘B’ is ‘D’:

(2 * 1) +2 (B is at index 1) => 4 (E)

Doubly Linked List Representation:

Like above we can represent Binary trees with, Non linear data structure Doubly Linked List.

In Doubly Linked List, Each node holds left and right child addresses along with value at that node.

Traversing Binary Trees:

To traverse the binary Tree there are 3 methods we use. The traversing aims to visit each node in a tree at least once.

• Pre-Order Traversal (from Root, Left then Right)
• In-Order Traversal (from Left, Root then Right Node)
• Post-Order Traversal (from Left, Right then Root Node)

Note: For all kinds of tree traversal, the time complexity will be always O(n), as we need to visit all the given nodes.

Java Code:

• Creation of a Binary Tree and Insertion of new Nodes
• Here we will implement a Binary Search Tree (sorted Binary Tree)

Delete a Node:

Deletion of a node from BST

Here Deepest node is left with a minimum of the subtree (from deleted Node)

PreOrder, Inorder and PostOrder Traversal code:

The print statement will print the value at the current node/root

Driver program:

Output for overall Program:

Thanks for your read and claps👏👏 👏 … Will explore other kinds of binary trees (AVL, RED-BLACK trees, etc..)in my next article.