Write a code that returns the deepest node in a binary tree. If the tree is complete, having two same depth of node, return the rightmost node.

Question

Utilisateur anonyme · Accepted Answer

//Last item in Breadth first search

class Node {
	int data;
	Node left;
	Node right;

	Node(int d) {
		data = d;
	}
	
	@Override
	public String toString() {
		return  "" + data;
	}
}

public class Tree {
	Node root;

	public static void main(String[] args) {

		Tree t = new Tree();
		t.root = new Node(5);
		t.root.left = new Node(10);
		t.root.right = new Node(20);
		t.root.left.left = new Node(15);
		t.root.right.right = new Node(19);

		System.out.println(t.deepestNode().data);
	}

	public Node deepestNode() {
		if (root == null) {
			return null;
		}
		ArrayList nodes = new ArrayList();
		nodes.add(root);
		Node deepest = null;
		while (!nodes.isEmpty()) {
			deepest = nodes.get(0);
			nodes.remove(0);
			if (deepest.left != null) {
				nodes.add(deepest.left);
			}
			if (deepest.right != null) {
				nodes.add(deepest.right);
			}
		}
		return deepest;
	}
}

just traverse the tree by level · Answer

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int v):val(v),left(NULL),right(NULL){} }; int findDeepestElement(TreeNode *root) { if(NULL==root) return -1; queue

q; q.push(root); q.push(NULL); vector tmp; while(!q.empty()) { TreeNode *p=q.front(); q.pop(); if(p) { tmp.push_back(NULL); if(p->left!=NULL) q.push(p->left); if(p->right) q.push(p->right); } else { if(q.empty()) return tmp[tmp.size()-1]; else q.push(NULL); tmp.clear(); } } }

xelways · Answer

class DeepestNode {
  int value;
  int level;
}

DeepestNode deepestNode(Node node, DeepestNode currentDeepest, int currentLevel) {
  if(node == null) return currentDeepest;

  if(currentLevel >= currentDeepest.level) {
    currentDeepest.level = currentLevel;
    currentDeepest.value = node.value;
  }

  currentDeepest = deepestNode(node.left, currentDeepest, currentLevel + 1);
  currentDeepest = deepestNode(node.right, currentDeepest, currentLevel + 1);

  return currentDeepest;
}

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois