Hierarchical data with parent & child relationships are very common, and Java collection does not have a Tree data structure, hence it is a popular interview question. Further questions include tree data structure processing using recursiion & iteration. A Tree data structure can be represented as shown below.
Step 1: A simple Node.java class that encapsulates its value,
…
Q. Traverse the tree in depth and return a list of all passed nodes. It should handle different data types as Double, String, etc. The interface for the tree node is
|
1 2 3 4 5 6 7 8 |
package tree; import java.util.List; public interface Node<E> { E getValue(); List<Node<E>> getChildren(); } |
A. Tree storing numbers: Tree storing text: #1. … Read more ›...
Q. Complete the following “TreeProcessingImpl” class ….. so that the unit tests shown below pass? Skeleton Code
|
1 2 3 4 5 6 7 8 |
package com.passing.unittests; import java.util.List; public interface Node<E> { E getValue(); List<Node<E>> getChildren(); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package com.passing.unittests; import java.util.List; public class NodeImpl<E> implements Node<E> { private E value; private List<Node<E>> children; public NodeImpl(E value, List<Node<E>> children) { this.value = value; this.children = children; } public E getValue() { return value; } public List<Node<E>> getChildren() { return children; } } |
|
1 2 3 4 5 6 |
package com.passing.unittests; public interface TreeProcessing<E> { abstract double getAverage(Node<E> node); abstract double getSum(Node<E> node); } |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
package com.passing.unittests; public class TreeProcessingImpl<E> implements TreeProcessing<Double> { public double getAverage(Node<Double> node) { return 0; } public double getSum(Node<Double> node) { return 0; } } |
Unit Tests
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
package com.passing.unittests; import java.util.Arrays; import java.util.List; import org.junit.Assert; import org.junit.Before; import org.junit.Test; public class TreeProcessingTest { private TreeProcessing<Double> tp = null; private Node<Double> numberRootNode; @Before public void init() { tp = new TreeProcessingImpl<Double>(); Node<Double> lvl2a = new NodeImpl<Double>(6.0, null); Node<Double> lvl2b = new NodeImpl<Double>(7.0, null); Node<Double> lvl2c = new NodeImpl<Double>(8.0, null); @SuppressWarnings("unchecked") List<Node<Double>> lvl2Children = Arrays.asList(lvl2a, lvl2b, lvl2c); Node<Double> lvl1a = new NodeImpl<Double>(5.0, lvl2Children); Node<Double> lvl1b = new NodeImpl<Double>(9.0, null); @SuppressWarnings("unchecked") List<Node<Double>> lvl1Children = Arrays.asList(lvl1a, lvl1b); numberRootNode = new NodeImpl<Double>(7.0, lvl1Children); } @Test public void testGetAverage() { Assert.assertEquals("Wrong", (6.0+7.0+8.0+5.0+9.0+7.0)/6, tp.getAverage(numberRootNode), 0.01); } @Test public void testSum() { Assert.assertEquals("Wrong", (6.0+7.0+8.0+5.0+9.0+7.0), tp.getSum(numberRootNode), 0.01); } } |
A. … Read more ›...
Q1. What are the different binary tree traversal mechanisms? A1. Traversing a tree means visiting all the nodes of a tree in order. Many different binary tree algorithms involve traversals. For example, if you wish to count the number of employees in an organizational chart you must visit each node....
Q1. Have you seen job advertisements requiring Java candidates to work in real-time or high volume transaction processing systems? A1. If you are applying for such jobs, you can be quizzed on Big O notation. Here are some basics to brush up on. … Read more ›...
Q. Write code to traverse a tree and get the largest “root-to-leaf sum”? A “root-to-leaf sum” is a sum of the node values in a root-to-leaf path.
|
1 2 3 4 5 6 7 8 |
package tree; import java.util.List; public interface Node<E> { E getValue(); List<Node<E>> getChildren(); } |
A. Let’s have a basic implementation of the above Node interface. … Read more ›...
Q. Write code test if a given tree is a binary search tree (i.e. BST)? A. A binary search tree (BST) is a binary tree where each node satisfies the following conditions: 1) key in any node is larger than the keys in all nodes in that node’s left subtree...
Q. Write code to traverse a tree and return the sum of the values (Node.getValue()) of all nodes at the level N in the binary tree?
|
1 2 3 4 5 6 7 8 |
package tree; public interface Node<E> { E getValue(); Node<E> getLeft(); Node<E> getRight(); } |
A. Let’s have a basic implementation of the above Node interface.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
package tree; public class NodeImpl<E> implements Node<E> { private E value; private Node<E> left; private Node<E> right; public NodeImpl(E value, Node<E> left, Node<E> right) { this.value = value; this.left = left; this.right = right; } public E getValue() { return value; } public Node<E> getLeft() { return left; } public Node<E> getRight() { return right; } } |
Here is the getLevelSum(root, … Read more ›...
Q. Write code to traverse a binary tree and get the largest “root-to-leaf sum”? A “root-to-leaf sum” is a sum of the node values in a root-to-leaf path.
|
1 2 3 4 5 6 7 8 |
package tree; public interface Node<E> { E getValue(); Node<E> getLeft(); Node<E> getRight(); } |
A. Let’s have a basic implementation of the above binary tree Node interface. … Read more ›...
Q. Write code to traverse a tree and return the sum of the values (Node.getValue()) of all nodes at the level N in the tree?
|
1 2 3 4 5 6 7 8 |
package tree; import java.util.List; public interface Node<E> { E getValue(); List<Node<E>> getChildren(); } |
A. Let’s have a basic implementation of the above Node interface. … Read more ›...
Java does not have a Tree class but you can define one. In my 10+ years as a Java developer, I have rarely used a Tree structure, but when I do use it I find it to be a bit more complicated than working with other data structure. … Read...
In the previous post entitled Java Tree structure interview questions and coding questions — Part 1, we looked at a very simple Tree structure. In this example, let’s look at a more complex tree structure with generics. Q. Write classes for a Tripple tree structue as shown below? … Read...
List, Set, Map, and Queue(access the ends FIFO or LIFO) are the basic Java data structure interfaces for which there are different implementations to cater for different usage patterns. Java data structure interview questions are very popular, … Read more ›...
