Diameter of a Tree
MediumPremium
Given the root of a binary tree, create a function diameterOfTree that determines and returns the length of the diameter of the tree, where the diameter of a tree is defined as the number of nodes along the longest path between any two nodes in the tree.
For example, given the following binary tree:
// tree 1 / \ 2 3 / \ 4 5
The diameter is 4, which is the length of the path [4, 2, 1, 3] or [5, 2, 1, 3].
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def diameterOfTree(root):
def heightOfTree(node, diameter):
if not node:
return 0
leftHeight = heightOfTree(node.left, diameter)
rightHeight = heightOfTree(node.right, diameter)
diameter[0] = max(diameter[0], leftHeight + rightHeight)
return max(leftHeight, rightHeight) + 1
diameter = [0]
heightOfTree(root, diameter)
return diameter[0]Watch Ali, SDE @ Amazon, answer the question: "Given the root of a binary tree, return the length of the diameter of the tree."
class Solution { static class Node { int data; Node left, right; public Node(int data) { this.data = data; left = null; right = null; } } static class Pair { int diameter; int height; public Pair(int diameter, int height) { this.diameter = diameter; this.height = height; } } static Pair solve(Node root){ //base case if(root == null){ return new Pair(0, 0); } Pair left = solve(root.left); Pair right = solve(root.right); int height = Math.max(left.height, right.height) + 1; int diameter = Math.max(left.height + right.height + 1 , Math.max(left.diameter , right.diameter)); return new Pair(diameter, height); } // Helper method to calculate the diameter static int diameterOfTree(Node root) { return solve(root).diameter; } public static void main(String[] args) { // debug your code below Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println(diameterOfTree(root)); } }