#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/lc-543-diameter-of-binary-tree-example-and-complexity-analysis

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/meta-interview-prep-v2/coding-patterns-ii-trees-graphs-advanced/lc-543-diameter-of-binary-tree-example-and-complexity-analysis

Repovive

LeetCode 543 Diameter of Binary Tree - Example and Complexity Analysis - Coding Patterns II: Trees, Graphs & Advanced | Meta Interview Prep | Repovive

Repovive.

Meta Interview Prep6 sections · 147 units8h total

Open in Course

LeetCode 543 Diameter of Binary Tree - Example and Complexity Analysis

Worked example

Consider this tree:

At node $4$ : left $= 0$ , right $= 0$ . Path through $4$ $= 0$ . Return depth $1$ .

At node $6$ : left $= 0$ , right $= 0$ . Path $= 0$ . Return depth $1$ .

At node $5$ : left $= 1$ (from $6$ ), right $= 0$ . Path $= 1$ . Return depth $2$ .

At node $2$ : left $= 1$ (from $4$ ), right $= 2$ (from $5$ ). Path $= 3$ . Return depth $3$ .

At node $1$ : left $= 3$ (from $2$ ), right $= 1$ (from $3$ ). Path $= 4$ . Maximum diameter is $4$ .

You visit each node once. $O(n)$ time, $O(h)$ space for the recursion stack where $h$ is the tree height.