How to make a binary tree in java


Java Algorithms: Linked List in Binary Tree (LeetCode) | by Ruslan Rakhmedov

Photo by Moritz Kindler on Unsplash

Task description:

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

  • The number of nodes in the tree will be in the range [1, 2500].
  • The number of nodes in the list will be in the range [1, 100].
  • 1 <= Node.val <= 100 for each node in the linked list and binary tree.

Reasoning:

Seems like this task forces us to use at least 2 different data structures, a binary tree and a linked list. Let’s introduce 2 simple classes to describe essential pieces which make the binary tree and linked list.

ListNode class which is used to build LinkedListTreeNode class which is used to build BinaryTree

You might notice some similarities between them. The only difference is that TreeNode has an additional pointer and that is all. In fact, you can represent some types of BinaryTrees using LinkedLists.

First example of BinaryTree which can be represented by LinkedListSecond example of BinaryTree which can be represented by LinkedList

Let’s have some fun and change our “angle of view”. The same thing can be done with the second example.

First example rotated to the left

Let’s get back to our task. We need to find out if a given binary tree contains a linked list in one of its path starting from any node. Don’t be scared by the task definition it’s easier than you think. Let’s talk about the brute force solution. What we can do is iterate through every node of the binary tree and starting from it iterate through the linked list. If we iterate through every node in the binary tree it’ll be O(n) — linear time complexity. Iteration over every node in the linked list will be O(n) as well. If for each node of the binary tree we iterate over linked list it’ll give us O(n²) — quadratic time complexity.

Sounds like a bad solution? Let’s have a look at provided numbers. The maximum number of nodes in binary tree is 2500. The maximum number of nodes in linked list is 100. 2500 * 100 = 250'000 maximum number of operations we will have to perform in order to solve the problem. Any modern CPU can process up to 10⁸ operations in less than one second. Our brute force solution has 2*10⁵.

Solution:

I’m going to implement the solution using a recursive approach, but it also can be solved by non recursively.

In the isSubPath method, we call the recursive method traverse

In the traverse function, we check if the current root node is null and as a result, we return whether or not the head is equal to null. If values in a node in a binary tree and in a node in the linked list are equals, we can try to verify if we found a match. To do it we call findPath method.

Otherwise, we continue exploring the binary tree by going to the left and right nodes.

In findPath method, we do almost the same thing we did in traverse. If the head is null means we reached the end of the linked list and we return true. If the root is null means we explored all nodes in a binary tree and we cannot continue. We return false. In all other cases, we check equality of values in nodes of a binary tree and a linked list. At the same time we try to explore both paths from the current node of binary tree, we try to go to the left child and right one. Any of the available paths will be sufficient for us to answer the main question — binary tree contains all nodes in provided linked list.

The full solution

As mentioned previously this solution has quadratic time complexity but it’s fine because we know the exact restrictions for the task. Testing system proves it.

Thanks for being a part of our community! More content in the Level Up Coding publication.
Follow: Twitter, LinkedIn, Newsletter
Level Up is transforming tech recruiting ➡️ Join our talent collective

Balancing a binary search tree · Applied Go

Get the Balance Right!

~ Depeche Mode

How a tree can get out of balance

As we have seen in last week’s article, search performance is best if the tree’s height is small. Unfortunately, without any further measure, our simple binary search tree can quickly get out of shape - or never reach a good shape in the first place.

The picture below shows a balanced tree on the left and an extreme case of an unbalanced tree at the right. In the balanced tree, element #6 can be reached in three steps, whereas in the extremely unbalanced case, it takes six steps to find element #6.

Unfortunately, the extreme case can occur quite easily: Just create the tree from a sorted list.

tree.Insert(1) tree.Insert(2) tree.Insert(3) tree.Insert(4) tree.Insert(5) tree.Insert(6) 

According to Insert’s logic, each new element is added as the right child of the rightmost node, because it is larger than any of the elements that were already inserted.

We need a way to avoid this.

A Definition Of “Balanced”

For our purposes, a good working definition of “balanced” is:

The heights of the two child subtrees of any node differ by at most one.

(Wikipedia: AVL-Tree)

Why “at most one”? Shouldn’t we demand zero difference for perfect balance? Actually, no, as we can see on this very simple two-node tree:

The left subtree is a single node, hence the height is 1, and the right “subtree” is empty, hence the height is zero. There is no way to make both subtrees exactly the same height, except perhaps by adding a third “fake” node that has no other purpose of providing perfect balance. But we would gain nothing from this, so a height difference of 1 is perfectly acceptable.

Note that our definition of balanced does not include the size of the left and right subtrees of a node. That is, the following tree is completely fine:

The left subtree is considerably larger than the right one; yet for either of the two subtrees, any node can be reached with at most four search steps. And the heights of both subtrees differs only by one.

How to keep a tree in balance

Now that we know what balance means, we need to take care of always keeping the tree in balance. This task consists of two parts: First, we need to be able to detect when a (sub-)tree goes out of balance. And second, we need a way to rearrange the nodes so that the tree is in balance again.

Step 1. Detecting an imbalance

Balance is related to subtree heights, so we might think of writing a “height” method that descends a given subtree to calculate its height. But this can be come quite costly in terms of CPU time, as these calculations would need to be done repeatedly as we try to determine the balance of each subtee and each subtree’s subree, and so on.

Instead, we store a “balance factor” in each node. This factor is an integer that tells the height difference between the node’s right and left subtrees, or more formally (this is just maths, no Go code):

balance_factor := height(right_subtree) - height(left_subtree) 

Based on our definition of “balanced”, the balance factor of a balanced tree can be -1, 0, or +1. If the balance factor is outside that range (that is, either smaller than -1 or larger than +1), the tree is out of balance and needs to be rebalanced.

After inserting or deleting a node, the balance factors of all affected nodes and parent nodes must be updated.

For brevity, this article only handles the Insert case.

Here is how Insert maintains the balance factors:

  1. First, Insert descends recursively down the tree until it finds a node n to append the new value. n is either a leaf (that is, it has no children) or a half-leaf (that is, it has exactly one (direct) child).
  2. If n is a leaf, adding a new child node increases the height of the subtree n by 1. If the child node is added to the left, the balance of n changes from 0 to -1. If the child is added to the right, the balance changes from 0 to 1.
  3. Insert now adds a new child node to node n.
  4. The height increase is passed back to n’s parent node.
  5. Depending on whether n is the left or the right child, the parent node adjusts its balance accordingly.

If the balance factor of a node changes to +2 or -2, respectively, we have detected an imbalance. At this point, the tree needs rebalancing.

Please enable JavaScript to view the animation.

Removing the imbalance

Let’s assume a node n that has one left child and no right child. n’s left child has no children; otherwise, the tree at node n would already be out of balance. (The following considerations also apply to inserting below the right child in a mirror-reversed way, so we can focus on the left-child scenario here.)

Now let’s insert a new node below the left child of n.

Two scenarios can happen:

1. The new node was inserted as the
left child of n’s left child.

Since n has no right children, its balance factor is now -2. (Remember, the balance is defined as “height of right tree minus height of left tree”. ) This is an easy case. All we have to do is to “rotate” the tree:

  1. Make the left child node the root node.
  2. Make the former root node the new root node’s right child.

Here is a visualization of these steps (click “Rotate”):

Please enable JavaScript to view the animation.

The balance is restored, and the tree’s sort order is still intact.

Easy enough, isn’t it? Well, only until we look into the other scenario…

2. The new node was inserted as the
right child of n’s left child.

This looks quite similar to the previous case, so let’s try the same rotation here. Click “Single Rotation” in the diagram below and see what happens:

Please enable JavaScript to view the animation.

The tree is again unbalanced; the root node’s balance factor changed from -2 to +2. Obviously, a simple rotation as in case 1 does not work here.

Now try the second button, “Double Rotation”. Here, the unbalanced node’s left subtree is rotated first, and now the situation is similar to case 1. Rotating the tree to the right finally rebalances the tree and retains the sort order.

Two more cases and a summary

The two cases above assumed that the unbalanced node’s balance factor is -2. If the balance factor is +2, the same two cases apply in an analogous way, except that everything is mirror-reversed.

To summarize, here is a scenario where all of the above is included - double rotation as well as reassigning a child node/tree to a rotated node.

Please enable JavaScript to view the animation.

The Code


Update: a version of this code using type parameters (a.k.a generics) is available in the article How I turned a binary search tree into a generic data structure with go2go · Applied Go


Now, after all this theory, let’s see how to add the balancing into the code from the previous article.

First, we set up two helper functions, min and max, that we will need later.

Imports, helper functions, and globals

How to represent a binary tree

Data structures: binary trees. Part 1

With this article, I begin a series of articles about well-known and not so data structures, as well as their application in practice.

In my articles I will give code examples in two languages ​​at once: in Java and in Haskell. Thanks to this, it will be possible to compare the imperative and functional styles of programming and see the pros and cons of both.

I decided to start with binary search trees, since this is a fairly basic, but at the same time an interesting thing, which, moreover, has a large number of modifications and variations, as well as applications in practice.

Why is this needed?

Binary search trees are commonly used to implement sets and associative arrays (eg set and map in c++ or TreeSet and TreeMap in java). More complex applications include ropes (I'll talk about them in a future article), various computational geometry algorithms, mainly in "scanning line" algorithms.

In this article, trees will be considered using an example of the implementation of an associative array. An associative array is a generalized array in which the indices (usually called keys) can be arbitrary.

Let's get started

A binary tree consists of vertices and links between them. More specifically, a tree has a distinguished root node, and each node can have left and right children. It sounds a little complicated in words, but if you look at the picture, everything becomes clear:

This tree will have node A as the root. F and I are both. Vertices without sons are usually called leaves.

Each vertex of X can be associated with its own tree, consisting of the vertex, its sons, sons of its sons, and so on. Such a tree is called a subtree rooted in X. Left and right subtrees of X are subtrees rooted respectively in the left and right sons of X. Note that such subtrees may be empty if X has no corresponding son.

Data in a tree is stored in its nodes. In programs, the tops of a tree are usually represented by a structure that stores data and two references to the left and right children. Missing vertices are denoted by null or the special constructor Leaf:

As you can see from the examples, we require keys to be comparable ( Ord a in haskell and T1 implements Comparable in java). All this is not casual - in order for the tree to be useful, the data must be stored in it according to some rules.

What are these rules? It's simple: if the key x is stored at the top of X, then only keys smaller (respectively larger) than x should be stored in the left (right) subtree. Let's illustrate:

What gives us such ordering? That we can easily find the required key x in the tree! Let's just compare x with the value at the root. If they are equal, then we have found what is required. If x is smaller (greater), then it can only be in the left (respectively, right) subtree. Let, for example, we are looking for the number 17: 9 in the tree0005

A function that receives a value by key:

Adding to the tree

Now let's try to add a new key/value pair (a,b). To do this, we will descend the tree as in the get function until we find a vertex with the same key, or we reach the missing son. If we found a vertex with the same key, then we simply change the corresponding value. Otherwise, it is easy to understand that it is in this place that a new vertex should be inserted so as not to disturb the order. Consider inserting key 42 into the tree in the previous figure:

Lyrical digression about the pros and cons of the functional approach

If you carefully consider the examples in both languages, you can see some difference in the behavior of the functional and imperative implementations: if in java we just modify data and links in existing vertices, then the haskell version creates new vertices along the entire path traversed by the recursion. This is because in purely functional languages ​​you cannot make destructive assignments. Clearly, this degrades performance and increases memory consumption. On the other hand, this approach also has positive aspects: the absence of side effects makes it much easier to understand how the program functions. You can read more about this in almost any textbook or introductory article about functional programming.

In the same article, I want to draw attention to another consequence of the functional approach: even after adding a new element to the tree, the old version will remain available! Due to this effect, ropes work, including in the implementation in imperative languages, allowing the implementation of strings with asymptotically faster operations than with the traditional approach. I will talk about ropes in one of the following articles.

Let's get back to our sheep

Now we've got to the most difficult operation in this article - removing the key x from the tree. To begin with, we, as before, find our vertex in the tree. Now there are two cases. Case 1 (remove number 5):

It can be seen that the vertex to be deleted does not have a right child. Then we can remove it and insert the left subtree instead of it without violating the order: it turns out - the left son may already have a right son. Let's do it differently: find the minimum in the right subtree. It is clear that it can be found if you start in the right son and go all the way to the left. Since the found minimum does not have a left son, we can cut it out by analogy with case 1 and insert it instead of the removed vertex. Due to the fact that it was minimal in the right subtree, the ordering property is not violated:

For dessert, a couple of functions that I used for testing:

Why is all this useful?

The reader may wonder why such complexity is needed when you can simply store a list of [(key, value)] pairs. The answer is simple - tree operations are faster. h vertices. This means that the complexity of operations in trees close to the optimum will be O(log(n)). Unfortunately, in the worst case, the tree may degenerate and the complexity of operations will be like that of a list, for example, in such a tree (it will turn out if you insert numbers 1..n in order):

Fortunately, there are ways to implement a tree in such a way that the optimal depth of the tree is preserved in any sequence of operations. Such trees are called balanced. These include, for example, red-black trees, AVL trees, splay trees, and so on.

Announcement of the next series

In the next article I will make a small overview of the various balanced trees, their pros and cons. In the following articles I will talk about some (possibly several) in more detail and with the implementation. After that, I will talk about the implementation of ropes and other possible extensions and applications of balanced trees.

Stay connected!

Useful Links

Whole source code for examples:

I also highly recommend reading the book by Cormen T. , Leizerson C., Rivest R.: "Algorithms: construction and analysis", which is an excellent textbook on algorithms and data structures

H Binary Tree or how to prepare a binary search tree in drafts

This article is about binary search trees. Recently I did an article about data compression using the Huffman method. There I did not really pay attention to binary trees, because the methods of searching, inserting, deleting were not relevant. Now I decided to write an article about trees. Perhaps we'll start.

A tree is a data structure consisting of nodes connected by edges. We can say that a tree is a special case of a graph. Here is an example tree:

This is not a binary search tree! Everything is under the cut!

Terminology

Root

The root of the tree is its topmost node. In the example, this is node A. In the tree, only one path can lead from the root to any other node! In fact, any node can be considered as the root of the subtree corresponding to this node.

Parents/children

All nodes except the root have exactly one edge leading up to another node. The node above the current one is called the parent of that node. The node located below the current one and connected to it is called descendant of this node. Let's take an example. Take node B, then its parent will be node A, and its children will be nodes D, E, and F.

A node that has no children will be called a leaf of the tree. In the example, nodes D, E, F, G, I, J, K will be leaves.

This is the basic terminology. Other concepts will be discussed later. So, a binary tree is a tree in which each node will have no more than two children. As you guessed, the tree from the example will not be binary, because nodes B and H have more than two children. Here is an example of a binary tree:

The nodes of the tree can contain any information. A binary search tree is a binary tree that has the following properties:

  1. Both left and right subtrees are binary search trees.
  2. All nodes of the left subtree of an arbitrary node X have data key values ​​less than the data key value of node X itself.

    Tree view

    As I go along, I will include some (perhaps incomplete) pieces of code in order to improve your understanding. The full code will be at the end of the article.

    The tree consists of nodes. Node structure:

    Each node has two children (it is quite possible that the leftChild and/or rightChild children will be null). You probably understood that in this case the number data is the data stored in the node; key - node key.

    We figured out the node, now let's talk about the pressing problems about trees. Here and below, the word "tree" will mean the concept of a binary search tree. Binary tree structure:

    As a class field, we only need the root of the tree, because from the root, using the getLeftChild() and getRightChild() methods, you can get to any node of the tree.

    Algorithms in a tree

    Search

    Let's say you have a built tree. How to find element with key key? You need to sequentially move from the root down the tree and compare the value of key with the key of the next node: if key is less than the key of the next node, then go to the left descendant of the node, if more - to the right, if the keys are equal - the desired node is found! Corresponding code:

    If current becomes null, then iteration has reached the end of the tree (at a conceptual level, you are in a non-existent place in the tree - a child of a leaf).

    Consider the efficiency of the search algorithm on a balanced tree (a tree in which nodes are distributed more or less evenly). Then the search efficiency will be O(log(n)), and the base 2 logarithm. See: if there are n elements in a balanced tree, then this means that there will be log(n) base 2 levels of the tree. And in the search, for one step of the cycle, you go down one level.

    Insertion

    Once you get the gist of the search, insertion should be easy to understand. You just need to go down to the leaf of the tree (according to the rules of descent described in the search) and become its descendant - left or right, depending on the key. Implementation:

    In this case, in addition to the current node, it is necessary to store information about the parent of the current node. When current becomes null, the parent variable will contain the sheet we need.
    The insertion efficiency will obviously be the same as that of the search - O(log(n)).

    Deletion

    Deletion is the most difficult operation to be performed on a tree. It is clear that first it will be necessary to find the element that we are going to remove. But then what? If we simply set its reference to null, then we will lose information about the subtree whose root is this node. Tree removal methods are divided into three cases.

    First case. The node to be deleted has no children

    If the node to be deleted has no children, it means that it is a leaf. Therefore, you can simply set the leftChild or rightChild fields of its parent to null.

    Second case. The node to be deleted has one child

    This case is also not very complicated. Let's go back to our example. Suppose we need to delete an element with key 14. Agree that since it is the right child of a node with key 10, then any of its descendants (in this case, the right one) will have a key greater than 10, so you can easily “cut” it from the tree, and connect the parent directly to the child of the node being deleted, i.e. connect the node with key 10 to node 13. The situation would be similar if we had to delete a node that is the left child of its parent. Think about it for yourself - an exact analogy.

    Third case. The node has two children

    The most difficult case. Let's take a look at a new example.

    Search for a successor

    Let's say we need to remove the node with the key 25. Whom shall we put in its place? One of his followers (descendants or descendants of descendants) must become the successor of (the one who takes the place of the removed node).

    How to understand who should be the successor? Intuitively, this is the node in the tree whose key is the next largest from the node being removed. The algorithm is as follows. You need to go to its right child (always to the right one, because it was already said that the key of the successor is greater than the key of the node being deleted), and then go through the chain of left children of this right child. In the example, we must go to the node with key 35, and then go down the chain of its left children to the leaf - in this case, this chain consists only of the node with key 30. Strictly speaking, we are looking for the smallest node in the set of nodes greater than the desired node.

    Successor search method code:

    Delete method complete code:

    Complexity can be approximated to O(log(n)).

    Finding the maximum/minimum in the tree

    Obviously, how to find the minimum/maximum value in the tree - you need to sequentially go through the chain of left/right elements of the tree, respectively; when you get to the leaf, it will be the minimum/maximum element.

    Symmetric traversal

    Traversal - visiting each node of the tree in order to do something with it.

    Recursive symmetrical traversal algorithm:

    1. Do action on left child
    2. Do action on self
    3. Do action on right child

    Conclusion

    Finally! If I didn’t explain something or have any comments, then I’m waiting in the comments. As promised, here is the complete code.

    Binary tree - binary search tree. Basic Binary Tree Operations (C#, Java)

    A binary tree is a hierarchical data structure in which each node has at most two child nodes. As a rule, the first node is called the parent node or the root of the tree (root), and the child nodes are called the left and right descendants.

    A binary tree is either empty or consists of data and two subtrees, each of which can be empty. Each subtree is in turn also a tree. Nodes without heirs are called leaves.

    For such a tree, the following conditions must be met:

    1. The left and right subtrees are also binary trees;
    2. All nodes in the left subtree of an arbitrary node x have data key values ​​less than the data key value of node x itself;
    3. All nodes in the right subtree of an arbitrary node x have data key values ​​greater than or equal to the data key value of node x itself.

    Basic binary tree operations

    The basic binary tree operations are adding an element to a tree , deleting an element and searching for an element in a tree . The complexity of each of these operations is O(log\,n) at best, and O(n) at worst. Depends on the balance of the tree.

    Example of a balanced binary tree (best case):

    Example of an unbalanced binary tree (worst case): Adding an element to the tree

    When adding element x to the tree, check the value of the current node.

    • If the value of the added element x is less than the value of the current node, we descend to the left subtree. If it doesn't exist, then we create it and assign the value to x . If it exists, then designate the left subtree as the current node and repeat from the beginning.
    • If the value of the added element x is greater than or equal to the value of the current node, descend to the right subtree. If it doesn't exist, then we create it and assign the value to x . If it exists, then designate the right subtree as the current node and repeat from the beginning. Adding an element to a binary tree this kind:

      Search for an element in a binary tree

      Start the search with the parent element. Let's say we're looking for the value 18 (let's call it x ). The search algorithm will look like this:

      1. x<33 — descend to the left subtree;
      2. x>5 — descend to the right subtree;
      3. x<20 — descend to the left subtree;
      4. x>17 — descend to the right subtree;
      5. x=18 - we found the element.

      The search for a non-existent element will come down to the fact that you will run into a non-existent node, and this will mean that the element you are looking for is not in the tree.

      Deleting an element from a binary tree

      Deleting leaves

      If the element to be deleted is a leaf, then simply delete the reference to this element from its parent (for example, to the value 31). Let's delete it.

      Removing a node that has a left subtree but no right subtree

      After removing 31, the element that has a left subtree but no right subtree is element 20. Remove it from the tree:

      1. Specify that the parent of element 17 will now be element 5.
      2. Specify that the right child of element 5 is now element 17.

      After deleting the values ​​31 and 20, the tree looks like this:

      Removing a node that has a right subtree but no left subtree parent element 5.
    • We specify element 5 that its right subtree is now element 18.

We get the following picture:0105

First case

The right subtree has no child.

To be able to consider this case, let's add element 34 to the tree: Remove element 35. To do this:

  1. Assign element 33 as parent to the right subtree (99);
  2. We assign element 34 as the left subtree;
  3. Element 34 specifies a new parent - 99;
  4. We indicate to the parent of the element to be deleted (33) that its right subtree is now element 99.

We get the following tree:

Second case

The right subtree has its own children.

Delete element 5. The first child (simultaneously the leftmost — the minimum in its subtree) of element 5 is element 18:

  1. We assign element 1 as the left node to element 18;
  2. Element 1 is assigned 18 as a parent;
  3. Element 33 (the parent of the element to be deleted) is specified as the left child node of element 18;
  4. For element 18, we specify element 33 as the parent (the parent of the element to be deleted).

The tree looks like this:

If the minimum left element has right children and is not the first child of the element being removed, then its right child is assigned to the parent of the minimum element of the right subtree.

In my code, I used a non-recursive delete mechanism.

Other removal mechanisms exist. You can visualize your tree at usfca.edu. You will notice that the deletion algorithm there is different from the one described above.

The tree class code in Java in my execution is as follows:

You can work with the class as follows:

We get the following output:

there are classes TreeSet and TreeMap , which are trees.

Top 40 Data Structure Questions and Algorithms for the Java Telegraph Interview

Coding

Stack:

Question 1: Implementing a stack using an array.

You need to implement a stack using an array. You need to write push and pop methods to demonstrate the stack (Last In First Out) behavior.

Solution : A Java program to implement a stack using an array.

Question 2: Implementing a stack using a linked list:

You need to implement a stack using a linked list. You need to write push and pop methods to demonstrate the stack (Last In First Out) behavior.

Solution : Java program to implement a stack using Linked List

Question 3: Implementing a stack using two queues.

You need to use two queues to implement stack behavior. You need to write push and pop methods to demonstrate the stack (Last In First Out) behavior.

Solution : Java program to implement a stack using two queues

Question 4: Sorting a stack using another stack

You need to sort a stack using a different stack. You can use the stack and pop operations for this.

Solution : Sort the stack using a different stack.

Linked list:

Question 5: Implementing a singly linked list in Java.

You must implement singly linked list data structures. You need to write a simple program to demonstrate insert, delete operations. Solution : A Java program to implement a singly linked list in Java.

Question 6: How to reverse a linked list in Java.

You need to write an iterative and recursive solution for a reverse linked list.

Solution : A Java program for a reverse linked list in Java.

Question 7: How to find the middle element of a linked list.

You need to write a Java program to find the middle element of a linked list in the most optimized way. Solution : A Java program to find the middle element of a linked list.

Question 8: How to find the nth element at the end of a linked list.

You need to write a Java program to find the nth element of a linked list in the best possible way.

In question 6, Node 7 is the third in the last linked list.

Solution : How to find the nth element at the end of the linked list.

Question 9: How to detect a loop in a linked list. If there is a loop in the linked list, find the starting node for the loop.

You need to write a Java program to determine if any cycle exists in a linked list, and if a cycle exists, you need to find the starting node for the linked list.

Solution : How to detect a loop in a linked list.

How to find the starting node of a loop in a linked list.

Question 10: How can I check if a linked list is a palindrome or not?

A palindrome is a word, phrase, number, or other sequence of characters or elements that reads the same forward or backward. For example: 12121 is a palindrome since it reads the same forward or backward. madam is also a palindrome. Therefore, we need to write Java programs to check if the linked list is a palindrome or not.

Solution : A Java program to check if a linked list is a palindrome.

Question 11: How to reverse a linked list in pairs?

You need to write a Java program to reverse-link a list in pairs. Solution: Java program to reverse link a list in a pair.

Binary tree:

Question 12: How can you go through a binary tree?

There are three ways to traverse a binary tree.

  • Pre-order
  • To
  • PostOrder.
Question 13: Write an algorithm to perform order traversal of a binary tree?

You need to write a Java program to traverse the binary tree level. You can use the queue data structure to traverse the order of the levels.

Solution : Binary tree traversal order level.

Question 14: Write an algorithm to perform a helical traversal of the order of a binary tree?

You need to write a Java program to traverse the spiral level in a binary tree

Solution : Sprial order or zigzag traversal of a binary tree.

Question 15: How can you print the leaf nodes of a binary tree?

You need to write a Java program to print all leaf nodes of a binary tree.

The end nodes for the above binary tree would be 5, 30, 55, 70

Solution : Print the end nodes of the binary tree.

Question 16: How to count the leaf nodes of a binary tree.

You need to write a Java program to count the leaf nodes of a binary tree.

The number of leaf nodes for the binary tree used in question 15 is 5 .

Solution : Count the leaf nodes of the binary tree.

Question 17. How to print all paths from root to leaf in a binary tree.

You need to write a program to print all paths from root to leaf.

Solution : Print all paths from root to leaf in a binary tree.

Question 18: How to find the node level in a binary tree

For a given node, you need to find the node level. For example: The node level would be 3 for node 70 used in Question 14.

Solution : Find the node level in the binary tree.

Question 19: How to find the maximum element in a binary tree.

You need to write a Java program to find the maximum element in a binary tree.

Solution : Find the maximum element in a binary tree.

Question 20: How to find the least common ancestor (LCA) in a binary tree.

You need to write a program to find the LCA in a binary tree.

Solution : Program to find LCA in binary tree.

Question 21: How to traverse the boundary of a binary tree.

Write a Java program to traverse the boundaries of a binary tree as shown in the figure below.

Solution: traversal of the binary tree boundary.

Question 22: How to print the vertical sum of a binary tree?

You need to find the sum of nodes that lie in one column.

Solution: How to display the vertical sum of a binary tree.

Binary search tree:

Question 23: What is a binary search tree?

A binary search tree is a special type of binary tree that has the following properties.

  • Nodes less than root will be in the left subtree.
  • Nodes that are greater than root will be a valid subtree.
  • Must not have duplicate nodes
  • Both left and right subtrees must also be a binary search tree.
Question 24: Can you write an algorithm to insert a node into a binary search tree.

Solution : Insert a node in a binary search tree

Question 25: Can you write an algorithm for removing a node in a binary search tree.

Solution : Delete node in binary search tree

Question 26: How can you find the minimum and maximum elements in a binary search tree?

Solution : The leftmost and rightmost nodes of the binary search tree are the minimum and maximum nodes, respectively.

The minimum and maximum elements in the binary search tree.

Question 27: How to find the least common ancestor (LCA) in a binary search tree.

You need to write a program to search for an LCA in a binary search tree.

Solution : A program to search for LCA in a binary search tree.

Sort:

Question 28: Can you write a merge sort algorithm and do you know the complexity of merge sort?

Solution : Implement Merge sort in Java

Question 29: What is binary search? Can you write an algorithm to find an element in a sorted array using binary search?

Solution : Java 9 Binary Search Algorithm0005

Array:

Question 30: Find the missing number in the array.

You are given an integer array containing 1 to n, but one of the numbers 1 to n is missing from the array. You need to provide an optimal solution to find the missing number. The number cannot be repeated in Arry.

For example:

 int[] arr1 = {7,5,6,1,4,2}; Missing number: 3 int[] arr2 = {5,3,1,2}; Missing number: 4 

Solution : Find the missing number in the array.

Question 31: Finding an element in a rotated and sorted array.

You are given a sorted and rotated array as shown below:

 int arr[] = {16,19,21,25,3,5,8,10}; 

If you notice that the array is sorted and rotated. You need to search for an element in the specified array in o(log n) time complexity.

Solution : Finding an element in a rotated and sorted array

Question 32: Finding the second largest number in array

Given an unsorted array, you need to find the second largest element in the array in o(n) time complexity.

For example:

 int[] arr1 = {7,5,6,1,4,2}; Second largest element in array: 6 

Solution: Java program to find the second largest number in an array.

Question 33: Find a number that occurs an odd number of times in an array

You are given an array of integers. All numbers occur an even number of times except for one. You need to find a number that occurs an odd number of times. You have to solve it with o(n) time complexity and o(1) space complexity.

For example:

 int array [] = new int [] {20, 40, 50, 40, 50, 20, 30, 30, 50, 20, 40, 40, 20}; Number that occurs an odd number of times: 50 

Solution: Java program to find a number that occurs an odd number of times in an array.

Question 34: Find the minimum number of platforms needed for a railway station
You are given the arrival and departure times of trains going to a particular station.
You need to find the minimum number of platforms needed to accommodate trains at any given time.

For example:

 arrival [] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00} departure[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00} Number of platforms required in the above scenario = 4 

Please note arrival times are in chronological order.

Solution: Find the minimum number of platforms required for a railway station.

Question 35: Find the pair whose sum is closest to zero in array

Given an array of +ve and -ve integers, we need to find a pair whose sum is close to zero in the array.

For example:

 array[] = {1,3, -5,7,8,20, -40,6}; The pair whose sum is closest to zero: -5 and 6 

Solution: Find the pair whose sum is closest to zero in an array in Java.

Question 36: Given a sorted array and a number x, find the pair in the array whose sum is closest to x

Given a sorted array, we need to find a pair whose sum is close to the number X in the array.

For example:

 array [] = {- 40, -5,1,3,6,7,8,20}; The pair whose sum is closest to 5: 1 and 3 

Solution: Find the pair whose sum is closest to X in an array in Java.

Question 37: Find all pairs of elements from an array whose sum is equal to a given number

Given an array, we need to find all pairs whose sum is equal to the number X.

For example:

 array [] = {-40, -5, 1, 3, 6, 7, 8, 20}; A pair of elements that sum to 15: 7, 8 and -5, 20 

Solution: Find all pairs of elements from an array whose sum is equal to a given number.

Graph:

Question 38: Write an algorithm for depth-first search in a graph.

Solution : depth-first search in java

Question 39: Write an algorithm for breadth-first search on a graph.

Solution: Java Breadth First Search

Diverse

Question 40: What is an algorithm and how to calculate the complexity of algorithms.

Learn more