count complete tree nodes | count complete tree nodes leetcode | leetcode 222 | tree

(00:00) Recursive Solution
(02:10) Making Use of Complete and Full BT Property

Algorithm
Get the height/depth of left-most branch - lh
Get the height/depth of right-most branch - rh
Case1: lh == rh it means tree is Full BT = Number of Nodes in Full BT of height h is 2^h - 1
Case2: lh != rh = recursively get the number of nodes from left and right sub-tree + 1 for current root node.

Time Complexity
In the worst case, we will have to keep making recursive calls to the bottom-most leaf nodes worst case will happen in case of tree last level only have one single node).
So we end up calling countNodes() h (height of tree) times.
Each time, we will have to do traversals along the left and right edges.

At level h, we iterate zero times (no child).
At level h - 1, you iterate once (one child and so on).
So if we add up all that is 0 + 1 + 2 + ... + h steps just to compute the left edges, which is h(1 + h)/2 = O(h^2).
For n - node complete tree we will have height h = O(logN)

Subscribe for more educational videos on data structure, algorithms and coding interviews.

#Tree #Recursive #Optimal #Coding #Complete_Binary_Tree #Programming #Interview #Practice #Leetcode #222 #Algorithm #Java #Preparation

[akhilmunna]

focus on the quality of the video. explanation is good