# DSA: Trees

##### What is Tree Data Structure?
• A tree data structure is made up of nodes that are connected via edges.
• The root node is the topmost node in a tree, and it is connected to zero or more child nodes.
• Each child node can have zero or more child nodes attached to it, establishing a hierarchical structure.
• Leaf nodes are nodes that have no child nodes.
• Except for the root node, which has no parent node, each node in a tree can have only one parent node.
• Siblings are nodes that share the same parent node.
• The number of edges from the root node to a node is its depth, and the height of a tree is the maximum depth of any node in the tree.
##### Basic terms used in Tree data structure:

Some basic terms used in tree data structure are:

1. Node: Each element in a tree is called a node.
2. Node degree: The number of direct children of a node is called the degree of that node. For example, in the above tree, the degree of node 2 is 2 because it has two children.
3. Root: The root node is the topmost node in the tree hierarchy. In other words, the root node is the one that doesn’t have any parent.
4. Parent: The node which is one level above any node is called its parent i.e. If the node contains any sub-node, then that node is said to be the parent of that sub-node.
5. Child: If the node is a descendant of any node, then the node is known as a child node.
6. Siblings: Nodes that share the same parent are called siblings.
7. Leaf: A node that does not have any children is called a leaf node or a terminal node.
8. Subtree: A tree consisting of a node and all its descendants is called a subtree.
9. Depth: The number of edges from the root to a given node is called its depth.
10. Height: The number of edges on the longest path from a node to a leaf is called its height.
11. Ancestor: A node that is on the path from the root to a given node is called an ancestor of that node.
12. Descendant: A node that is below a given node in a tree is called a descendant of that node.
##### Implementation of Tree:

There are two main ways to implement trees: using an array and using linked lists.

• Array Implementation: A binary tree is represented by an array in the array implementation. The root node is saved at index 1, the left child of a node at index i is stored at index 2i, and the right child of a node at index i is stored at index 2i+1. This technique is typically used for complete binary trees, where all levels but the last are filled.
``````class BinaryTree {
int[] tree;
int size;

public BinaryTree(int size) {
this.size = size;
this.tree = new int[size + 1]; // add 1 for 1-indexing
}

// insert a new node into the tree
public void insert(int value) {
if (size == tree.length - 1) {
System.out.println("Tree is full.");
return;
}
size++;
tree[size] = value;
}

// get the value of the parent node of a given index
public int parent(int index) {
return tree[index / 2];
}

// get the value of the left child node of a given index
public int leftChild(int index) {
return tree[2 * index];
}

// get the value of the right child node of a given index
public int rightChild(int index) {
return tree[2 * index + 1];
}
}
``````

Time Complexity:O(1)
Space Complexity: O(n)

• Linked List Implementation: Each node of the tree is represented as a separate object or node in the linked list implementation, having references or pointers to its sibling nodes. There are two kinds of linked list implementations:
• Singly Linked List: Each node has a reference to only one child node, i.e., either the left child or the right child.
• Doubly Linked List: Each node has references to both the left and the right child nodes.
``````public class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;

public TreeNode(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
}
}

public class BinaryTree {
TreeNode root;

public BinaryTree() {
root = null;
}

public void insert(int data) {
TreeNode newNode = new TreeNode(data);

if (root == null) {
root = newNode;
} else {
TreeNode current = root;
TreeNode parent;

while (true) {
parent = current;

if (data < current.data) {
current = current.leftChild;

if (current == null) {
parent.leftChild = newNode;
return;
}
} else {
current = current.rightChild;

if (current == null) {
parent.rightChild = newNode;
return;
}
}
}
}
}

public void printInorderTraversal(TreeNode node) {
if (node != null) {
printInorderTraversal(node.leftChild);
System.out.print(node.data + " ");
printInorderTraversal(node.rightChild);
}
}

public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();

binaryTree.insert(50);
binaryTree.insert(30);
binaryTree.insert(70);
binaryTree.insert(20);
binaryTree.insert(40);
binaryTree.insert(60);
binaryTree.insert(80);

System.out.print("Inorder Traversal: ");
binaryTree.printInorderTraversal(binaryTree.root);
}
}
``````

Time Complexity: O(log n) to O(n) for insertion and O(n) for inorder traversal

Space Complexity: O(n)

##### Tree traversal techniques:

In tree data structure, there are two main traversal techniques:

1. Depth-First Traversal: We study the deepest nodes of the tree data structure first, then progress up towards the root node in depth-first traversal. This technique is mostly used to investigate the structure of a tree.

There are three types of depth-first traversal:

• Inorder Traversal: In inorder traversal, we first traverse the left subtree, then the root node and then the right subtree.
`````` public void inorderTraversal(Node node) {
if (node == null) {
return;
}
inorderTraversal(node.left);
System.out.print(node.data + " ");
inorderTraversal(node.right);
}``````
• Preorder Traversal: In preorder traversal, we first traverse the root node, then the left subtree and then the right subtree.
``````  public void printPreorder(Node node) {
if (node == null)
return;

System.out.print(node.data + " ");
printPreorder(node.left);
printPreorder(node.right);
}``````
• Postorder Traversal: In postorder traversal, we first traverse the left subtree, then the right subtree and then the root node.
``````void postorder(Node node) {
if (node == null)
return;

// Traverse left subtree
postorder(node.left);

// Traverse right subtree
postorder(node.right);

// Visit root node
System.out.print(node.data + " ");
}``````
1. Breadth-First Traversal: In breadth-first traversal, we explore the level of the node by level starting from the root node. This technique is mostly used to locate a node or to determine the shortest path between two nodes.

``````import java.util.LinkedList;
import java.util.Queue;

class Node {
int value;
Node left, right;

Node(int value) {
this.value = value;
this.left = this.right = null;
}
}

public class BFS {
Node root;

BFS() {
root = null;
}

void printLevelOrder() {
if (root == null)
return;

while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.value + " ");

if (node.left != null)

if (node.right != null)
}
}

public static void main(String[] args) {
BFS tree = new BFS();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

System.out.println("BFS Traversal of Binary Tree:");
tree.printLevelOrder();
}
}
``````

Time Complexity: O(n)

Space Complexity: O(n)