Output: 6

Solution

Method 1 - Basic Brute Force

Code

[{"language":"Java","code":"public int countNodes(TreeNode root) {\n    if (root == null)\n        return 0;\n    return 1 + countNodes(root.left) + countNodes(root.right);\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> countNodes</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(TreeNode root) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    if</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (root </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">==</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> null</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">)</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        return</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 0</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    return</span><span style=\"color:#005CC5;--shiki-dark:#79B8FF\"> 1</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> +</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> countNodes</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root.left) </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">+</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> countNodes</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(root.right);</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">}</span></span></code></pre>"}]

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(n) assuming recursion stack

Method 2 - Calculate Left Most and RIght Most Heights

Steps to solve this problem:

get the height of left-most part
get the height of right-most part
when they are equal, the # of nodes = 2^h -1
when they are not equal, recursively get # of nodes from left&right sub-trees

Case 1 - When Left and Right Most Height Are Equal

Refer the diagram below, then number of nodes = 2 ^h - 1 =

Related Tags