instagram

Google Interview Tree node with x and y value on same level

by omt

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

}
Share