Given an arbitrary tree starting at “root” where each node contains a pair of values (x, y), write a boolean function find(Node root, int x, int y) that returns true iff
* x is equal to a value “x” of any node n1 in the tree
* and y is equal to a value “y” of any node n2 in the tree
* and both n1 and n2 are at the same level in the tree
boolean find(Node root, int x, int y)
Example:
(1,120)
/ | \
/ | \
/ | \
(5,15) (30,70) (80,110)
/ | \ |
/ | \ |
/ | \ |
(35, 40) (45,50) (55, 65) (90, 100)
boo == true
find(root, 45, 100) == true
find(root, 30, 100) == false
find(root, 30, 70) == true
find(root, 70, 30) == false
Algorithm
package com.omt.learn.algo; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import com.omt.learn.algo.util.tree.TreeNodeWithValue; public class TreeNodeValueAtLevel { public static void main(String[] args) { System.out.println("Find In Same Level :" + isXandYInSameLevel(generateTree(), 37, 23)); } public static boolean isXandYInSameLevel(TreeNodeWithValue root, int x, int y) { Map<Integer, List<TreeNodeWithValue>> nodeAtEachLevelMap = new HashMap<>(); List<TreeNodeWithValue> listOfNodes = new ArrayList<>(); listOfNodes.add(root); int level = 0; nodeAtEachLevelMap.put(level, listOfNodes); while (nodeAtEachLevelMap.containsKey(level)) { List<TreeNodeWithValue> list = new ArrayList<>(); boolean xFound = false; boolean yFound = false; for (TreeNodeWithValue tn : nodeAtEachLevelMap.get(level)) { if (!xFound && tn.x == x) { xFound = true; } if (!yFound && tn.y == y) { yFound = true; } if (xFound && yFound) { return true; } if (tn.leftNode != null) { list.add((TreeNodeWithValue) (tn.leftNode)); } if (tn.rightNode != null) { list.add((TreeNodeWithValue) tn.rightNode); } } ++level; if (!list.isEmpty()) { nodeAtEachLevelMap.put(level, list); } } return false; } public static TreeNodeWithValue generateTree() { TreeNodeWithValue AVL = new TreeNodeWithValue( new TreeNodeWithValue(new TreeNodeWithValue(27, 37, "D"), new TreeNodeWithValue(17, 78, "E"), 37, 88, "B"), new TreeNodeWithValue(null, new TreeNodeWithValue(25, 44, "F"), 22, 23, "C"), 1, 120, "A"); return AVL; } }
TreeNodeWithValue.java
package com.omt.learn.algo.util.tree; public class TreeNodeWithValue extends TreeNode { public int x = 0; public int y = 0; public TreeNodeWithValue(int x, int y, String name) { super(name); this.x = x; this.y = y; } public TreeNodeWithValue(TreeNodeWithValue left, TreeNodeWithValue right, int x, int y, String name) { super(left, right, name); this.x = x; this.y = y; } }
TreeNode.java
public class TreeNode { public String nodeName = ""; public boolean isVisited = false; public int value = 0; public TreeNode leftNode = null; public TreeNode rightNode = null; public TreeNode parentNode = null; public TreeNode() { // TODO Auto-generated constructor stub } public TreeNode(String name) { nodeName = name; } public TreeNode(TreeNode left, TreeNode right, String name) { leftNode = left; rightNode = right; nodeName = name; setParent(); } private void setParent() { if (leftNode != null) { leftNode.parentNode = this; } if (rightNode != null) { rightNode.parentNode = this; } } }