# <IAMSUMAN/> # Binary Tree<T> implementation using Dart

Binary trees are a fundamental data structure in computer science, often used for searching and sorting algorithms. They are a tree-like data structure where each node can have at most two children, referred to as the left and right children.

Here is a diagram of a binary tree:

``````        8
/ \
/   \
/     \
/       \
5        10
/ \      / \
2   6    9  12
``````

In the above diagram, the node with the value 8 is the root node of the tree. The nodes with the values 5 and 10 are its children, and so on. Each node in the tree can be thought of as a separate tree in itself, with its own set of children.

The advantage of using a binary tree is that it allows for fast searching, insertion, and deletion. Because each node has at most two children, the height of the tree is logarithmic in the number of nodes, resulting in efficient algorithms.

Here is an implementation of a `Node` class in Dart:

``````class Node<T> {
T data;
Node<T>? left;
Node<T>? right;
Node({required this.data});
}
``````

In the above code, we have defined a generic class `Node` with three properties: `data`, `left`, and `right`. The `data` holds the value of the current node, and the `left` and `right` properties hold the references to the left and right child nodes respectively.

Here is an implementation of the abstract class `Tree`

``````abstract class Tree<T> {
Node<T> _insert(Node<T>? node, T data);
bool _search(Node<T>? node, T data);
void _inOrderTraversal(Node<T>? node);
void _postOrderTraversal(Node<T>? node);
void _preOrderTraversal(Node<T>? node);
}
``````

The above code is an abstract class called `Tree` that defines a generic type `T`. This class contains several methods that are related to the operations that can be performed on a tree data structure such as insert, search, inorder traversal, postorder Traversal, and preorder Traversal.

The `_insert` method takes in two parameters: a node of type `Node<T>` and data of type `T`. This method is responsible for inserting a new node into the tree with the given data.

The `_search` method takes in two parameters: a node of type `Node<T>` and data of type `T`. This method is responsible for searching for a specific node in the tree with the given data.

The `_inOrderTraversal` method takes in a single parameter: a node of type `Node<T>`. This method is responsible for traversing the tree in an in-order fashion, visiting the left subtree first, then the root, and finally the right subtree.

The `_postOrderTraversal` method takes in a single parameter: a node of type `Node<T>`. This method is responsible for traversing the tree in a post-order fashion, visiting the left subtree first, then the right subtree, and finally the root.

The `_preOrderTraversal` method takes in a single parameter: a node of type `Node<T>`. This method is responsible for traversing the tree in a pre-order fashion, visiting the root first, then the left subtree, and finally the right subtree.

It is important to notice that all the methods are marked as abstract, this means that these methods are not implemented in this class and must be implemented in a derived class.

Now, let's define the Binary Tree class and some operations that can be performed on a binary tree.

``````class BinaryTree<T extends Comparable> implements Tree<T> {
Node<T>? root;
//some operation..
}
``````

The class `BinaryTree<T extends Comparable>` is a generic class that implements the `Tree<T>` interface. The generic type `T` is constrained to types that extend the `Comparable` class, which means that the type must have a `compareTo` method defined. This is used in the insert and search methods to compare the data of nodes in the tree.

The class has a nullable property `root` of type `Node<T>?` which is the root of the binary tree.

The class `BinaryTree` implementation of `Tree` abstract class which means it has to implement all the methods of the tree interface.

### Insert:

``````void insert(T data) {
root = _insert(root, data);
}

@override
Node<T> _insert(Node<T>? node, T data) {
if (node == null) {
return Node(data: data);
}
if (data.compareTo(node.data) <= 0) {
node.left = _insert(node.left, data);
} else {
node.right = _insert(node.right, data);
}
return node;
}
``````

The `insert()` is used to insert new data into the binary tree. This method uses the private helper method `_insert()` to recursively find the correct location to insert the new data. If the current node is `null`, a new node with the data is returned. Otherwise, the `compareTo()` is used to compare the data to the data of the current node. If the data is less than or equal to the current node's data, the `left` property is updated with the result of calling `_insert()` on the left child node. Otherwise, the `right` property is updated with the result of calling `_insert()` on the right child node.

``````bool search(T data) {
return _search(root, data);
}

@override
bool _search(Node<T>? node, T data) {
if (node == null) {
return false;
}
if (node.data == data) {
return true;
}
if (data.compareTo(node.data) <= 0) {
return _search(node.left, data);
} else {
return _search(node.right, data);
}
}
``````

The `search()` is used to search for a specific piece of data in the binary tree. Like the `insert()` method, this method uses a private helper method `_search()` to recursively search the binary tree.

If the current node is `null`, the data is not in the binary tree and `false` is returned. If the current node's data is equal to the search data, `true` is returned.

Otherwise, the `compareTo()` is used to determine if the search data is less than or greater than the current node's data.

If the search data is less than the current node's data, `_search()` is called on the left child node. Otherwise, `_search()` is called on the right child node.

### In-order, Pre-order & Post-order Traversal:

``````void inOrderTraversal() {
_inOrderTraversal(root);
}

void preOrderTraversal() {
_preOrderTraversal(root);
}

void postOrderTraversal() {
_postOrderTraversal(root);
}

@override
void _inOrderTraversal(Node<T>? node) {
if (node != null) {
_inOrderTraversal(node.left);
print(node.data);
_inOrderTraversal(node.right);
}
}

@override
void _postOrderTraversal(Node<T>? node) {
if (node != null) {
print(node.data);
_postOrderTraversal(node.left);
_postOrderTraversal(node.right);
}
}

@override
void _preOrderTraversal(Node<T>? node) {
if (node != null) {
_preOrderTraversal(node.left);
_preOrderTraversal(node.right);
print(node.data);
}
}
``````

he `inOrder()`, `preOrder()`, and `postOrder()` methods are used to traverse the binary tree and print out the data in the nodes.

Each of these methods uses a private helper method with the same name but with a leading underscore, such as `_inOrder()`, to recursively traverse the binary tree.

The `inOrder()` first recursively calls itself on the left child node, then prints the current node's data, and finally recursively calls itself on the right child node.

The `preOrder()` method prints the current node's data, recursively calls itself on the left child node, and finally recursively calls itself on the right child node.

The `postOrder()` method recursively calls itself on the left child node, recursively calls itself on the right child node, and finally prints the current node's data.

here is an implementation full code of Binary tree:

``````class Node<T> {
T data;
Node<T>? left;
Node<T>? right;
Node({required this.data});
}

abstract class Tree<T> {
Node<T> _insert(Node<T>? node, T data);
bool _search(Node<T>? node, T data);
void _inOrderTraversal(Node<T>? node);
void _postOrderTraversal(Node<T>? node);
void _preOrderTraversal(Node<T>? node);
}

class BinaryTree<T extends Comparable> implements Tree<T> {
Node<T>? root;
void insert(T data) {
root = _insert(root, data);
}

@override
Node<T> _insert(Node<T>? node, T data) {
if (node == null) {
return Node(data: data);
}
if (data.compareTo(node.data) <= 0) {
node.left = _insert(node.left, data);
} else {
node.right = _insert(node.right, data);
}
return node;
}

bool search(T data) {
return _search(root, data);
}

@override
bool _search(Node<T>? node, T data) {
if (node == null) {
return false;
}
if (node.data == data) {
return true;
}
if (data.compareTo(node.data) <= 0) {
return _search(node.left, data);
} else {
return _search(node.right, data);
}
}

void inOrderTraversal() {
_inOrderTraversal(root);
}

void preOrderTraversal() {
_preOrderTraversal(root);
}

void postOrderTraversal() {
_postOrderTraversal(root);
}

@override
void _inOrderTraversal(Node<T>? node) {
if (node != null) {
_inOrderTraversal(node.left);
print(node.data);
_inOrderTraversal(node.right);
}
}

@override
void _postOrderTraversal(Node<T>? node) {
if (node != null) {
print(node.data);
_postOrderTraversal(node.left);
_postOrderTraversal(node.right);
}
}

@override
void _preOrderTraversal(Node<T>? node) {
if (node != null) {
_preOrderTraversal(node.left);
_preOrderTraversal(node.right);
print(node.data);
}
}
}
``````

In conclusion, binary trees are a powerful and versatile data structure with many uses in computer science. They allow for efficient searching, insertion, and deletion, and their logarithmic height makes them well-suited for algorithms that require fast performance. Understanding binary trees is essential for understanding more complex data structures and algorithms.