Binary trees are a fundamental data structure in computer science, widely used for representing hierarchical data. In this blog post, we will delve into the concept of binary trees, their implementation in Java, traversal algorithms, and some common operations associated with them.

**Understanding Binary Trees**

**What is a Tree?**

A tree is a non-linear data structure used for storing data. It is comprised of nodes and edges without any cycles. Each node in a tree can point to n number of other nodes within the tree. It serves as a way to represent hierarchical structures, with a parent node called the root and multiple levels of additional nodes.

- It’s a non-linear data structure used for storing data
- It is made up of nodes and edges without having any cycle. // its so important
- Each node in a tree can point to n number of nodes in a tree
- It is a way of representing a hierarchical structure with a parent node called a root and many levels of additional nodes

**What is a Binary Tree?**

A binary tree is a hierarchical data structure composed of nodes, where each node has at most two children, referred to as the left child and the right child. The topmost node of the tree is called the root node. Each node contains a data element and references to its left and right children (or null if the child does not exist).

In simple words, A tree is called a binary tree if each node has zero, one, or two children.

```
1
/ \
2 3
/ \
4 5
```

Binary trees are commonly used in various applications such as expression trees, binary search trees, and more.

**How to represent a Binary Tree in java?**

**TreeNode Representation:**

`null<-----|left|data|right|------>null`

**Structure of TreeNode in a Binary Tree:**

To represent a binary tree in Java, we can create a `TreeNode`

class to define the structure of each node in the tree. Here’s how we can do it:

```
public class TreeNode {
private int data; // Data of the node
private TreeNode left; // Pointer to the left child node
private TreeNode right; // Pointer to the right child node
// Constructor to initialize the node with data
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
// Getters and setters for the data, left, and right pointers
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
```

In this `TreeNode`

class:

- Each node has a
`data`

field to store the value of the node. - Each node has a
`left`

field to store a reference to its left child node. - Each node has a
`right`

field to store a reference to its right child node. - The constructor initializes the node with the given data and sets both left and right pointers to null initially.

With this `TreeNode`

class, you can create instances of the `TreeNode`

class to represent each node in the binary tree. You can then use these instances to build the binary tree by setting the left and right pointers of each node accordingly. The root of the binary tree is typically represented by a reference to the topmost node in the tree. Initially, if the tree is empty, the root reference is set to null. As you add nodes to the tree, you update the root reference accordingly.

In simple words, Initially, the root node points to null. When we create any temporary node to insert into the tree, such as a temporary node with 15 as its data and left and right node pointers pointing to null, we can then add more nodes to the left or right.

**How to implement a binary tree in java?**

Let’s start by implementing a basic binary tree structure in Java:

```
public class BinaryTree {
private TreeNode root; // Created one root node of TreeNode type
private class TreeNode {
private TreeNode left;
private TreeNode right;
private int data;
public TreeNode(int data) {
this.data = data;
}
}
public void createBinaryTree() {
TreeNode first = new TreeNode(1);
TreeNode second = new TreeNode(2);
TreeNode third = new TreeNode(3);
TreeNode fourth = new TreeNode(4);
TreeNode fifth = new TreeNode(5);
root = first; // root ---> first
first.left = second;
first.right = third; // second <--- first ---> third
second.left = fourth;
second.right = fifth;
}
public static void main(String[] args) {
BinaryTree bt = new BinaryTree();
bt.createBinaryTree();
}
}
```

This `BinaryTree`

class represents a simple binary tree. It has a nested class `TreeNode`

which represents each node in the binary tree. The `createBinaryTree`

method initializes the tree structure by creating nodes and linking them appropriately. Finally, the `main`

method demonstrates creating an instance of `BinaryTree`

and initializing it.

**Traversal Algorithms**

Traversal is the process of visiting all the nodes in a tree in a specific order. There are three common methods for traversing binary trees:

**In-order traversal**: Visit the left subtree, then the root, and finally the right subtree.**Pre-order traversal**: Visit the root, then the left subtree, and finally the right subtree.**Post-order traversal**: Visit the left subtree, then the right subtree, and finally the root.

Let’s implement these traversal algorithms in Java.

**Pre-Order Traversal Of Binary Tree in Java**

- Visit the root node.
- Traverse the left subtree in pre-order fashion.
- Traverse the right subtree in pre-order fashion.

**Recursive Pre-Order Traversal**

It recursively traverses the tree in the following order: root, left subtree, right subtree.

```
public void preOrder(TreeNode root) {
if(root == null) {
return;
}
System.out.print(root.data + " ");
preOrder(root.left);
preOrder(root.right);
}
```

In this code:

- If the root is null, indicating an empty subtree, the method returns.
- If the root is not null, it prints the data of the current node, traverses the left subtree recursively, and then traverses the right subtree recursively.

Consider the following binary tree:

```
1
/ \
2 3
/ \
4 5
```

In pre-order traversal, the order of node visits would be: **1, 2, 4, 5, 3**.

**Here’s how the execution progresses:**

`pre_order_traversal(1)`

– Visit root node 1.`pre_order_traversal(2)`

– Visit root node 2.`pre_order_traversal(4)`

– Visit root node 4.`pre_order_traversal(None)`

– Backtrack to the previous call (`pre_order_traversal(4)`

), finish left subtree traversal.`pre_order_traversal(5)`

– Visit root node 5.`pre_order_traversal(None)`

– Backtrack to the previous call (`pre_order_traversal(5)`

), finish left subtree traversal.`pre_order_traversal(None)`

– Backtrack to the previous call (`pre_order_traversal(2)`

), finish left subtree traversal.`pre_order_traversal(3)`

– Visit root node 3.`pre_order_traversal(None)`

– Backtrack to the previous call (`pre_order_traversal(3)`

), finish right subtree traversal.`pre_order_traversal(None)`

– Backtrack to the previous call (`pre_order_traversal(1)`

), finish right subtree traversal.

And the output of the traversal will be:

`Pre-order traversal: 1 2 4 5 3`

In this execution, we maintain a call stack. For each method call, we track the line number and the root node being passed to that method. When we reach the base condition, we backtrack to the previous calls and execute the next steps.

**Iterative Pre-Order Traversal Of Binary Tree**

Iterative pre-order traversal is a way to traverse a binary tree iteratively, without using recursion. we utilize the stack data structure. Initially, we push the root node onto the stack. While the stack is not empty, we iterate using a while loop and perform pre-order traversal operations. As long as the stack is not empty, we pop the top node from the stack and assign it to the temp node. We then print its data. Since in pre-order traversal, we first visit the left node and then the right node, while pushing nodes into the stack, we need to push the right node first and then the left node so that we process the left node first (due to LIFO).

```
public void IterativePreOrder() {
if(root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()) {
TreeNode temp = stack.pop();
System.out.println(temp.data);
if(temp.right != null) {
stack.push(temp.right);
}
if(temp.left != null) {
stack.push(temp.left);
}
}
}
```

This method `iterativePreOrder`

performs an iterative pre-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It prints the data of each node as it visits them. If a node has a right child, it is pushed onto the stack first so that it is visited after the left child (since pre-order traversal visits the left subtree before the right subtree). Finally, the method returns once all nodes have been visited.

Consider the following binary tree:

```
1
/ \
2 3
/ \
4 5
```

The iterative pre-order traversal will visit the nodes in the order: 1, 2, 4, 5, 3.

**Here’s how the execution goes step by step:**

- Start with an empty stack and initialize the current node as the root.
- Push the root node onto the stack.
- While the stack is not empty, do the following:
- a. Pop the top node from the stack and process it (print its value or perform any other desired operation).
- b. Push the right child onto the stack if it exists.
- c. Push the left child onto the stack if it exists.

**Let’s execute the algorithm step by step:**

- Start with an empty stack: Stack = []
- Push the root node (1) onto the stack: Stack = [1]
- Pop the top node from the stack (1), process it: Output = [1], Stack = []
- Push the right child (3) onto the stack: Stack = [3]
- Push the left child (2) onto the stack: Stack = [3, 2]
- Pop the top node from the stack (2), process it: Output = [1, 2], Stack = [3]
- Push the right child (5) onto the stack: Stack = [3, 5]
- Push the left child (4) onto the stack: Stack = [3, 5, 4]
- Pop the top node from the stack (4), process it: Output = [1, 2, 4], Stack = [3, 5]
- There’s no left or right child for node 4, so proceed.
- Pop the top node from the stack (5), process it: Output = [1, 2, 4, 5], Stack = [3]
- There’s no left or right child for node 5, so proceed.
- Pop the top node from the stack (3), process it: Output = [1, 2, 4, 5, 3], Stack = []
- The stack is empty, so the traversal is complete.

The output of the iterative traversal is: **[1, 2, 4, 5, 3]**, which is the pre-order traversal of the given binary tree.

During the execution of iterative pre-order traversal, we follow the described algorithm. We push the root node onto the stack initially. Then, as long as the stack is not empty, we pop nodes from the stack, print their data, and push their right and left children onto the stack accordingly.

**In Order Binary Tree traversal**

- Traverse the left subtree in In-order fashion.
- Visit the root node.
- Traverse the right subtree in In-order fashion.

In-order traversal of a binary tree involves visiting the left subtree in in-order fashion, then visiting the root node, and finally traversing the right subtree in in-order fashion.

**Recursive In-Order Binary Tree Traversal**

In Recursive In-order traversal, we visit each node in the tree in the following order:

- Recursively traverse the left subtree.
- Visit the root node.
- Recursively traverse the right subtree.

```
public void RecursiveInOrder(TreeNode root) {
if(root == null) { // base case
return;
}
RecursiveInOrder(root.left);
System.out.print(root.data + " ");
RecursiveInOrder(root.right);
}
```

In this code:

- If the root is null, indicating an empty subtree, the method returns.
- If the root is not null, it recursively traverses the left subtree, then prints the data of the current node, and finally recursively traverses the right subtree.
- This process effectively traverses the tree in an in-order sequence.

Consider the same binary tree:

```
1
/ \
2 3
/ \
4 5
```

In in-order traversal, the order of node visits would be: 4, 2, 5, 1, 3.

Here’s how the execution progresses:

`in_order_traversal(1)`

– Traverse left subtree.`in_order_traversal(2)`

– Traverse left subtree.`in_order_traversal(4)`

– Visit root node 4.`in_order_traversal(None)`

–**Backtrac**k to the previous call (`in_order_traversal(4)`

), finish left subtree traversal.- Print root node 2.
`in_order_traversal(5)`

– Visit root node 5.`in_order_traversal(None)`

–**Backtrack**to the previous call (`in_order_traversal(5)`

), finish left subtree traversal.- Print root node 1.
`in_order_traversal(3)`

– Traverse right subtree.- Print root node 3.
`in_order_traversal(None)`

–**Backtrack**to the previous call (`in_order_traversal(1)`

), finish right subtree traversal.

And the output of the traversal will be:

`In-order traversal:4 2 5 1 3`

During the execution of recursive in-order traversal, we maintain a method call stack. For each method call, we keep track of the line number and the root node being passed to that method. Initially, we pass the root node to this method. Then, we visit the left subtree of the root node, print the root node’s data, and finally visit the right subtree of the root node. This tracking of each recursive method call, line number, and root node helps during backtracking.

**Iterative In Order Traversal of binary tree in java**

In iterative in-order traversal, we visit the left node first, then perform in-order traversal for that node, come back to print the root node’s data, and finally visit the right node to perform its in-order traversal.

To achieve this, we create a stack of TreeNodes and initialize a temp node with the root node. We traverse the tree until the stack is not empty or temp is not null (indicating there are nodes to traverse or backtrack).

If temp is not null, we push it onto the stack and move to its left child. If temp is null, indicating we have reached a leaf node, we pop the top node from the stack, print its data, and move to its right child. This process continues until all nodes are traversed.

```
public void iterativeInOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode temp = root;
while (!stack.isEmpty() || temp != null) {
if (temp != null) {
stack.push(temp);
temp = temp.left;
} else {
temp = stack.pop();
System.out.print(temp.data + " ");
temp = temp.right;
}
}
}
```

This method `iterativeInOrderTraversal`

performs an iterative in-order traversal of the binary tree. It starts from the root node and uses a stack to keep track of nodes to be visited. It traverses the left subtree first, then visits the current node, and finally traverses the right subtree. If a node has a left child, it is pushed onto the stack and the left child becomes the current node. If a node does not have a left child or has already been visited, it is popped from the stack, its data is printed, and its right child becomes the current node. The traversal continues until all nodes have been visited and the stack is empty.

Consider the same binary tree:

```
1
/ \
2 3
/ \
4 5
```

The iterative in-order traversal will visit the nodes in the order: 4, 2, 5, 1, 3.

**Here’s how the execution goes step by step:**

- Start with an empty stack and initialize the current node as the root.
- Push the root node onto the stack and move to the left child until reaching a null node.
- When a null node is reached, pop the top node from the stack, process it (print its value or perform any other desired operation), and move to its right child.

**Let’s execute the algorithm step by step:**

- Start with an empty stack: Stack = []
- Push the root node (1) onto the stack and move to the left child: Stack = [1], Current Node = 1
- Move to the left child of 1 (2) and push it onto the stack: Stack = [1, 2], Current Node = 2
- Move to the left child of 2 (4) and push it onto the stack: Stack = [1, 2, 4], Current Node = 4
- The left child of 4 is null, so pop 4 from the stack, process it: Output = [4], Stack = [1, 2], Current Node = 2
- Move to the right child of 4 (null), so no action needed: Output = [4], Stack = [1, 2], Current Node = 2
- Process node 2: Output = [4, 2], Stack = [1], Current Node = 2
- Move to the right child of 2 (5) and push it onto the stack: Stack = [1, 5], Current Node = 5
- The left child of 5 is null, so process node 5: Output = [4, 2, 5], Stack = [1], Current Node = 5
- Move to the right child of 5 (null), so no action needed: Output = [4, 2, 5], Stack = [1], Current Node = 5
- Process node 1: Output = [4, 2, 5, 1], Stack = [], Current Node = 1
- Move to the right child of 1 (3) and push it onto the stack: Stack = [3], Current Node = 3
- The left child of 3 is null, so process node 3: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
- Move to the right child of 3 (null), so no action needed: Output = [4, 2, 5, 1, 3], Stack = [], Current Node = 3
- The stack is empty, so the traversal is complete.

The **output **of the traversal is: **[4, 2, 5, 1, 3]**, which is the in-order traversal of the given binary tree.

**Post Order traversal of Binary Tree**

- Traverse the left subtree in Post-order fashion.
- Traverse the right subtree in Post-order fashion.
- Visit the root node.

**Recursive Post-Order Traversal of Binary Tree**

In recursive post-order traversal, we visit each node in the tree in the following order:

- Recursively traverse the left subtree.
- Recursively traverse the right subtree.
- Visit the root node.

```
1
/ \
2 3
/ \
4 5
```

In post-order traversal, the order of node visits would be: 4, 5, 2, 3, 1.

```
public void RecursivePostOrder(TreeNode root) {
if(root == null) {
return;
}
RecursivePostOrder(root.left);
RecursivePostOrder(root.right);
System.out.print(root.data + " ");
}
```

In this code:

- If the root is null, indicating an empty subtree, the method returns.
- If the root is not null, it recursively traverses the left subtree, then recursively traverses the right subtree, and finally prints the data of the current node.
- This process effectively traverses the tree in a post-order sequence.

**Here’s how the execution progresses:**

`post_order_traversal(1)`

– Traverse left subtree.`post_order_traversal(2)`

– Traverse left subtree.`post_order_traversal(4)`

– Visit root node 4.`post_order_traversal(None)`

– Backtrack to the previous call (`post_order_traversal(4)`

), finish left subtree traversal.`post_order_traversal(5)`

– Visit root node 5.`post_order_traversal(None)`

– Backtrack to the previous call (`post_order_traversal(5)`

), finish left subtree traversal.- Print root node 2.
`post_order_traversal(3)`

– Traverse right subtree.- Print root node 3.
`post_order_traversal(None)`

– Backtrack to the previous call (`post_order_traversal(3)`

), finish right subtree traversal.- Print root node 1.
`post_order_traversal(None)`

– Backtrack to the previous call (`post_order_traversal(1)`

), finish right subtree traversal.

And the output of the traversal will be:

`Post-order traversal: 4 5 2 3 1`

In recursive post-order traversal, we utilize a method call stack. For each recursive call, we visit the left and right nodes respectively, and then print the data of the root node.

To illustrate this, we maintain a method call stack where we track the line number and the root node being passed to that method. This approach ensures that we visit the left and right subtrees first before printing the data of the root node.

**Iterative post-order traversal of a binary tree**

Iterative post-order traversal is a bit more complex compared to pre-order and in-order traversals because you need to ensure that you visit the left and right subtrees before processing the root node. One common approach to achieve this iteratively is to use two stacks.

```
public void iterativePostOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);
while (!stack1.isEmpty()) {
TreeNode temp = stack1.pop();
stack2.push(temp);
if (temp.left != null) {
stack1.push(temp.left);
}
if (temp.right != null) {
stack1.push(temp.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().data + " ");
}
}
```

This method `iterativePostOrderTraversal`

performs an iterative post-order traversal of the binary tree. It starts from the root node and uses two stacks to keep track of nodes to be visited. It pushes nodes onto `stack2`

in a pre-order traversal (root, right, left) using `stack1`

. After traversing all nodes, it pops nodes from `stack2`

to print their data, resulting in a post-order traversal (left, right, root). The traversal continues until all nodes have been visited and both stacks are empty.

**Here’s how the execution goes step by step:**

- Start with two empty stacks:
`Stack1`

and`Stack2`

. Initialize the current node as the root. - Push the root node onto
`Stack1`

. - While
`Stack1`

is not empty, do the following: a. Pop the top node from`Stack1`

and push it onto`Stack2`

. b. Push the left child onto`Stack1`

if it exists. c. Push the right child onto`Stack1`

if it exists. - Once
`Stack1`

is empty, all nodes have been pushed onto`Stack2`

. Pop nodes from`Stack2`

to get the post-order traversal.

**Let’s execute the algorithm step by step:**

- Start with two empty stacks:
`Stack1 = [], Stack2 = []`

. - Push the root node (1) onto
`Stack1`

:`Stack1 = [1]`

. - Pop the top node from
`Stack1`

(1) and push it onto`Stack2`

:`Stack2 = [1]`

. - Push the right child (3) onto
`Stack1`

:`Stack1 = [3]`

. - Push the left child (2) onto
`Stack1`

:`Stack1 = [3, 2]`

. - Pop the top node from
`Stack1`

(2) and push it onto`Stack2`

:`Stack2 = [1, 2]`

. - Push the right child (5) onto
`Stack1`

:`Stack1 = [3, 5]`

. - Push the left child (4) onto
`Stack1`

:`Stack1 = [3, 5, 4]`

. - Pop the top node from
`Stack1`

(4) and push it onto`Stack2`

:`Stack2 = [1, 2, 4]`

. - Pop the top node from
`Stack1`

(5) and push it onto`Stack2`

:`Stack2 = [1, 2, 4, 5]`

. - Pop the top node from
`Stack1`

(3) and push it onto`Stack2`

:`Stack2 = [1, 2, 4, 5, 3]`

. - All nodes have been processed and pushed onto
`Stack2`

. - Pop nodes from
`Stack2`

to get the post-order traversal: Output = [4, 5, 2, 3, 1].

The **output** of the traversal is: [4, 5, 2, 3, 1], which is the post-order traversal of the given binary tree.

**Level order traversal of a Binary Tree in Java**

In level order traversal, also known as breadth-first traversal, we visit each node level by level. To achieve this, we use a queue data structure. Initially, we add the root node to the queue. Then, we iterate while the queue is not empty.

During each iteration, we dequeue a node from the queue and assign it to the temp node. We print the data of this node. If the temp node has left and/or right children, we enqueue them into the queue. This ensures that we traverse the tree level by level, visiting each node before moving on to its children.

This approach is useful for applications like level-wise printing of a binary tree or finding the shortest path in a graph represented as a tree.

```
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode temp = queue.poll();
System.out.print(temp.data + " ");
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
// o/p : 1,2,3,4,5
```

This code performs a level-order traversal of the binary tree using a queue. It starts from the root node and adds it to the queue. Then, it repeatedly dequeues nodes from the queue, prints their data, and enqueues their left and right children if they exist. This process continues until all nodes in the tree have been visited.

**Bonus: Binary Search in Java **

Binary search in Java is a searching algorithm commonly applied to arrays or lists. It is used to find the position of a target value within a sorted array or list.

Binary trees, on the other hand, are a data structure consisting of nodes in a hierarchy, where each node has at most two children, referred to as the left and right child. Binary search trees (BSTs) are a specific type of binary tree where the values are stored in a sorted order, and each node’s value is greater than all values in its left subtree and less than all values in its right subtree.

While binary search and binary trees share the term “binary,” they are distinct concepts and are not directly related in terms of implementation. However, binary search trees leverage the principles of binary search to efficiently search, insert, and delete elements. The property of binary search trees ensures that searching for a value can be performed efficiently, similar to binary search in sorted arrays.

**Here’s the explanation and execution of the binary search algorithm in Java**

```
int low = 0;
int high = nums.length - 1;
while(low <= high) {
int mid = (high + low) / 2;
if(nums[mid] == key) {
return mid;
}
if(key < nums[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
```

In binary search, we look into the array until the `low`

index becomes greater than the `high`

index. We iterate until this condition holds true.

First, we find the `mid`

index of the array using the formula `(high + low) / 2`

.

If we find the `key`

at the exact `mid`

position, we return that `mid`

index.

If the `key`

is less than the value at the `mid`

index, it means our `key`

is in the first half of the array. So, we update `high`

to `mid - 1`

and continue searching in that half.

If the `key`

is greater than the value at the `mid`

index, it means our `key`

is in the right side of the array. So, we update `low`

to `mid + 1`

and continue searching in that half.

If we don’t find the `key`

in the array, we return -1, indicating that the `key`

is not present in the array.

**Let’s execute the algorithm step by step:**

```
nums[]: 1, 10, 20, 47, 59, 65, 75, 88, 99
key: 65
low = 0, high = 8
Iteration 1:
mid = (0 + 8) / 2 = 4
nums[mid] = 59
Since key (65) > nums[mid], update low = mid + 1 = 4 + 1 = 5
low = 5, high = 8
Iteration 2:
mid = (5 + 8) / 2 = 6
nums[mid] = 75
Since key (65) < nums[mid], update high = mid - 1 = 6 - 1 = 5
low = 5, high = 5
Iteration 3:
mid = (5 + 5) / 2 = 5
nums[mid] = 65
Since key (65) == nums[mid], return mid = 5 (key found at index 5)
Key 65 found at index 5 in the array.
```

**Code**

```
public class BinarySearch {
public int binarySearch(int[] nums, int key) {
int low = 0;
int high = nums.length - 1;
while (low <= high) {
int mid = (high + low) / 2;
if (nums[mid] == key) {
return mid;
}
if (key < nums[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
BinarySearch bs = new BinarySearch();
int[] nums = {1, 10, 20, 47, 59, 65, 75, 88, 99};
int key = 65;
System.out.println(bs.binarySearch(nums, key));
}
}
```

This `BinarySearch`

class implements the binary search algorithm to find the index of a key in a sorted array. The `binarySearch`

method takes an array of integers (`nums`

) and a key to search for. It initializes the low and high pointers to the start and end indices of the array, respectively. Then, it iteratively calculates the mid index, compares the key with the element at the mid index, and updates the low and high pointers accordingly based on whether the key is smaller or larger than the mid element. If the key is found, the method returns the index of the key; otherwise, it returns -1. The `main`

method demonstrates how to use the `binarySearch`

method to search for a key in a sorted array and prints the index of the key.

**Conclusion**

Binary trees are powerful data structures that offer efficient storage and retrieval of hierarchical data. Understanding their implementation and traversal algorithms is crucial for any Java programmer. By mastering binary trees, you’ll be equipped to tackle a wide range of programming challenges that involve hierarchical data representation and manipulation.