Advanced
Data Structures Algorithms & System Design(HLD+LLD)
by Logicmojo

⌚ Define Binary Tree

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.

⌚ What is a leaf node?

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

⌚ What is root node?

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

⌚ What is the most common way to implement Binary Heap?

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

⌚ What is Binary Heap?

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.

⌚ What is a binary search tree?

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.

⌚ How do you convert a binary tree into a binary search tree?

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.

⌚ What is the best way to implement a Tree data structure? Give us some code.

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;
    }
}

⌚ What are advantages and disadvantages of BST?

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.

⌚ What is a Balanced Tree, and why does it matter?

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.

⌚ Implement Pre-order Traversal of Binary Tree using Recursion

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);
}

⌚ What is AVL Tree?

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

⌚ How do you delete a node from a binary search tree in Java?

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.

⌚ How do you find the binary tree's lowest common ancestor (LCA)?

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.

⌚ Classify Tree Traversal Algorithms?

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.

⌚ How can you determine whether a binary tree is a subtree of another binary tree?

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.

⌚ In a binary tree, how do you calculate the distance between two nodes?

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.

⌚How can we do Iterative Pre-order Traversal of a Binary Tree without Recursion?

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;
}

⌚ What is the distinction between a Binary tree and a Trie tree?

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.

⌚ How do you tell whether two trees are the same?

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

⌚ In a binary tree, how do you count the number of leaf nodes?

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

⌚ What is the Red-Black tree data structure?

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.

⌚ What is Morris traversal, and how does it work?

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.

⌚ In a binary tree, how do you find the minimum and maximum elements?

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.

⌚ What Is the Average Time Complexity to Find Height of 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)

⌚ What is diameter of a Tree

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.

⌚ What is Degree of a Node?

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.

🚀Conclusion

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.

TEST YOUR KNOWLEDGE!