Back to home
## Tree Data Structure

A data structure is a specialised way for organising and storing data in a computer so that it may be used more efficiently. Stacks, linked lists, and queues
are examples of data

structures that are organised in a sequential sequence. A linked data structure, for example, is made up of a collection of nodes connected by links or points.

Similarly, a tree data structure is a hierarchical data structure that is organised in a tree-like structure. It is made up of a core node, structural nodes, and sub nodes that are linked together via edges. The roots, branches, and leaves of a tree data structure are all connected to one another.

If you're interviewing for a job as a Java Developer or a software engineer, you can be asked multiple questions about this topic. Answering questions
based on binary trees, binary search trees, and related programmes might be difficult for applicants. In this article, we'll look at some of the most often
requested binary tree interview questions. This article will

assist you in better comprehending the notion and preparing you to land your dream job!

The amount of children each node can have in a normal tree is unrestricted. A binary tree is made up of nodes, each of which has a "left" and "right" pointer as well as a data element.

🚀 Types of Binary Tree

• Full binary tree: Every node other than leaf nodes has 2 child nodes.

• Complete binary tree: All levels are filled except possibly the last one, and all nodes are filled in as far left as possible.

• Perfect binary tree: All nodes have two children and all leaves are at the same level.

A leaf node is a node in a binary tree or a tree that does not have any offspring.

The root node is the initial node, or the top node, in a tree.

An array is widely used to implement binary heaps. Any binary tree can be stored in an array, but a binary heap can be stored compactly because it is always a complete binary tree. Pointers don't take up any space; instead, arithmetic on array indices can be used to get the parent and children of each node:

The root element is 0

Left child : (2*i)+1

Right child : (2*i)+2

Parent child : (i-1)/2

A Binary Heap is a Binary Tree that possesses the following characteristics:

It's a full-fledged tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). Because to this property,
Binary Heap can be stored in an array.

It's either a Min Heap or a Max Heap in a Binary Heap. In a Min Binary Heap, the root key must be the smallest of all the keys in the Binary Heap. For all nodes in a Binary Tree, the same property must be true recursively. MinHeap is comparable to Max Binary Heap.

A binary search tree (BST) is a form of binary tree where each internal node has a key. The rule for a binary search tree is:

A key can be greater than all of the keys in the left subtree of a node.

A node's right subtree can have a key that is smaller than all the keys in the subtree.

If n1 is a node with the key 8, then every node in n1's left subtree will have keys less than 8, and every node in n1's right subtree will have keys larger than 8.

A binary tree differs from a binary search tree in that the BST follows the rule that the left subtree should have lower key values and the right subtree should have higher key values. This can be accomplished by employing the following traversal techniques:

Make a temporary array to store the tree's inorder traverse.

The temporary array should be sorted. Any sorting algorithm can be used here.

Perform an inorder traversal of the tree once more.

One by one, copy the array elements to each tree node.

That's a basic (generic) tree structure for String or any other object:

public class Tree<T> { private Node<T> root; public Tree(T rootData) { root = new Node<T>(); root.data = rootData; root.children = new ArrayList<Node<T>>(); } public static class Node<T> { private T data; private Node<T> parent; private List<Node<T>> children; } }

Advantages of BST:

We can always keep the cost of insert(), delete(), and lookup() to O(logn) if we use a balanced binary search tree

When it comes to search, insert, and delete, BST is much faster than an array.

In comparison to other data structures, the code is straightforward.

Disadvantages of BST:

At access, BST is somewhat slower than an array.

A binary search tree can become degenerated or out of balance (imbalanced).

A balanced binary search tree (using some self-balancing method) - AVL tree, Red-Black tree, Splay tree - should always be implemented. Otherwise, the cost of operations may not be logarithmic, and the process may devolve into a linear array search.

Only when all three conditions are met is a tree said to be balanced:

The height difference between the left and right subtrees is no more than one.

The subtree on the left is well-balanced.

The right subtree is balanced

Height-balancing requirement:

If the heights of its subtrees deviate by no more than one, a node in a tree is height-balanced.

If all of the nodes in a tree are balanced in height, it is said to be height-balanced.

The height of a balanced BST is log n, where n is the number of items in the tree. The height of the tree can be up to n in the worst case and in an imbalanced BST, making it similar to a linked list. Each operation (search, insertion, and deletion) takes time O(n) in the worst case, which can be avoided.

Starting from the root node of the tree, we must execute the following three things for every node N in order to traverse a (non-empty) binary tree in pre-order fashion:

Root node process

(L) Traverse the left subtree recursively. When this stage is completed, we will be back at the beginning i.e, root.

(R) Traverse the right subtree recursively. We'll be back at root once this phase is completed.

Time complexity of the traversal is O(n) and Space Complexity: O(n)

// Recursive function to perform pre-order traversal of the tree public static void preorder(TreeNode root) { // return if the current node is empty if (root == null) { return; } // Display the data part of the root (or current node) System.out.print(root.data + " "); // Traverse the left subtree preorder(root.left); // Traverse the right subtree preorder(root.right); }

Height-balancing binary search trees are known as AVL trees. It's called after the AVL tree's creators, Adelson-Velsky and Landis. The AVL tree compares the heights of the left and right sub-trees and ensures that they do not deviate by more than one. The Balance Factor is the name given to this disparity. This allows us to search the AVL tree for an element in O(log n), where n is the number of elements.

The height difference is defined as the balancing factor of a node (N) in a binary tree:

Our tree is unbalanced if the balance factor does not equal -1,0, or 1, and we must do specific operations (called rotations) to balance it. One or more of the following tree rotations is required:

Left Rotation

Right Rotation

Left - Right Rotation

Right - Left Rotation

The deletion of a BST can be difficult since its attributes must be retained after the operation. Let's take a look at each of the three scenarios:

A leaf node is the node that will be eliminated. Remove the node by simply removing it.

There is only one child in the node that will be eliminated. Copy the child to the node and delete the child in this example.

There are two children in the node that will be eliminated.

Find the node's inorder successor in this example. The content of the inorder successor can then be copied to the node and the inorder successor can be deleted.

Let's look at two binary tree nodes, n1 and n2.

The shared ancestor of n1 and n2 that is positioned farthest from the root is known as the lowest common ancestor (LCA).

To locate the LCA, use the approach described below.

Create an array with the route from the root node to n1.

Create an array with the route from the root node to n2.

Continue along both pathways until the value in both arrays is the same.

Algorithms for traversing trees can be divided into two groups:

DFS - Depth First Search

BFS - Breadth First Search

There are three types of depth-first search (DFS) algorithms.

Preorder Traversal (current-left-right)— Visit the current node before going to any of the subtrees on the left or right.

Visit the current node after visiting all nodes in the left subtree but before visiting any nodes in the right subtree in an inorder traversal (left-current-right).

Postorder Traversal (left-right-current) — After visiting all of the nodes in the left and right subtrees, go to the current node.

BFS has only one variant

Level Order Traversal — At the same level, visit nodes one by one in a left-to-right pattern.

Consider we have a binary tree T. We now want to check if a binary tree S is a subtree of T.

To begin, look to see if there is a node in T that is also in S.

Once you've located this common node, see if the nodes below are also part of S.

If this is the case, we can reasonably conclude that S is a subtree of T.

Consider two binary tree nodes, n1 and n2, respectively. The least number of edges that must be crossed to get from one node to the other is equal to the distance between n1 and n2. It's crucial to remember that you travel the shortest path between the nodes.

We can try this using stack

First set current node as root

Check the base case i.e., if current node is null then return

Store current node value in the answer array

Put right of root in stack

Put left of root in stack

While stack is not empty we pop out from stack into current node. Please note that the left will be on top of stack and will be taken first

Repeat from step 2 until we find our final answer

public List<Integer> preorderTraversal(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> rst = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.empty()) { TreeNode node = stack.pop(); rst.add(node.val); if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return rst; }

The trie's nodes do not store their associated key, unlike a binary search tree. Instead, the key with which a node is associated is determined by its position in the trie. This disperses the value of each key throughout the data structure, implying that not every node must have a value associated with it.

If two binary trees contain the same data and arrangement, they are identical. By visiting both trees and comparing their data and arrangements, this can be accomplished.

This is the algorithm that will allow us to achieve it:

Examine the root node's data (tree1 data ==tree2 data).

Recursively check the left subtree. tree1-> left subtree, tree2-> left subtree) = sameTree

Similarly we check for right subtree

If above are satisfied then we return 1

Here's an iterative approach for calculating the binary tree's total number of leaf nodes:

First check if root is null then return zero

Initalise count = 0

Push root in stack data structure

Start Loop until Stack is not empty.

Pop the last node from stack and push its left and right children if they are not null

A red-black tree is a self-balancing binary search tree with one extra bit at each node, which is commonly read as the colour (red or black). These colours are used to keep the tree balanced as insertions and deletions are made.

The tree's balance isn't ideal, but it's good enough to cut down on searching time and keep it around O(log n), where n is the total number of components in the tree.

Morris (InOrder) traversal is a recursive tree traversal algorithm that does not need a stack or recursion. Linkages are formed as successors in this traversal, and nodes are printed utilising these links. Finally, the adjustments are undone to bring the tree back to its original state.

Algorithm

Set the root to be the current node curr.

Check if curr has a left child when it is not NULL.

If curr lacks a left child, print curr and update it to point to the node to curr's right.

Otherwise, make curr the right child of curr's left subtree's rightmost node.

Curr should be updated to this left node.

Because all elements less than or equal to a given root node are on the left, iterating the leftmost region of the tree yields the least element in the Binary tree.

Similarly, elements larger than or equal to a certain root node will be to the right, thus iterating the rightmost region of the tree will yield the highest element in a Binary tree.

Because the nodes are either part of the left or right sub tree, the user does not need to traverse all of them, resulting in a complexity of less than n. Time complexity will be O in the typical scenario, provided nodes are uniformly distributed (logn)

The diameter of a tree is the length of the longest path between any 2 nodes of a tree. The length of a path is counted as the number of edges lying on that path. Remember that this node is not compulsory to pass through the root node of the tree.

The degree of a node refers to the total number of subtrees associated to it. A leaf node's degree must be zero. The maximum degree of a node among all the nodes in the tree is the tree's degree. The node {3} has a degree of 3.

We have now reached the end of this page. With the knowledge from this page, you should be able to create your own programmes with some research, and it's in fact recommended to hone your programming skills with small projects. There is no way to cover all the information you need to be a successful programmer in one course. In fact, programming is a constant learning process, regardless of whether you are a seasoned professional developer or a newbie.