Commitf201a57

authored

clarify space complexity for dfs trees (neetcode-gh#3761)

1 parent232acfa commitf201a57Copy full SHA for f201a57

File tree

+20

-4

lines changed

+20

-4

lines changed

Lines changed: 5 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -526,7 +526,11 @@ class Solution {`
`526`	`526`	`###Time & Space Complexity`
`527`	`527`
`528`	`528`	`* Time complexity: $O(n)$`
`529`		`-* Space complexity: $O(n)$`
	`529`	`+* Space complexity: $O(h)$`
	`530`	`+* Best Case ([balanced tree](https://www.geeksforgeeks.org/balanced-binary-tree/)): $O(log(n))$`
	`531`	`+* Worst Case ([degenerate tree](https://www.geeksforgeeks.org/introduction-to-degenerate-binary-tree/)): $O(n)$`
	`532`	`+`
	`533`	`+>Where $n$ is the number of nodes in the tree and $h$ is the height of the tree.`
`530`	`534`
`531`	`535`	`---`
`532`	`536`

Lines changed: 5 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -520,7 +520,11 @@ class Solution {`
`520`	`520`	`###Time & Space Complexity`
`521`	`521`
`522`	`522`	`* Time complexity: $O(n)$`
`523`		`-* Space complexity: $O(n)$`
	`523`	`+* Space complexity: $O(h)$`
	`524`	`+* Best Case ([balanced tree](https://www.geeksforgeeks.org/balanced-binary-tree/)): $O(log(n))$`
	`525`	`+* Worst Case ([degenerate tree](https://www.geeksforgeeks.org/introduction-to-degenerate-binary-tree/)): $O(n)$`
	`526`	`+`
	`527`	`+> Where $n$ is the number of nodes in the treeand $h$ is the height of the tree.`
`524`	`528`
`525`	`529`	`---`
`526`	`530`

Lines changed: 5 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -176,7 +176,11 @@ class Solution {`
`176`	`176`	`###Time & Space Complexity`
`177`	`177`
`178`	`178`	`* Time complexity: $O(n)$`
`179`		`-* Space complexity: $O(n)$`
	`179`	`+* Space complexity: $O(h)$`
	`180`	`+* Best Case ([balanced tree](https://www.geeksforgeeks.org/balanced-binary-tree/)): $O(log(n))$`
	`181`	`+* Worst Case ([degenerate tree](https://www.geeksforgeeks.org/introduction-to-degenerate-binary-tree/)): $O(n)$`
	`182`	`+`
	`183`	`+>Where $n$ is the number of nodes in the tree and $h$ is the height of the tree.`
`180`	`184`
`181`	`185`	`---`
`182`	`186`

Lines changed: 5 additions & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -191,7 +191,11 @@ class Solution {`
`191`	`191`	`###Time & Space Complexity`
`192`	`192`
`193`	`193`	`* Time complexity: $O(n)$`
`194`		`-* Space complexity: $O(n)$`
	`194`	`+* Space complexity: $O(h)$`
	`195`	`+* Best Case ([balanced tree](https://www.geeksforgeeks.org/balanced-binary-tree/)): $O(log(n))$`
	`196`	`+* Worst Case ([degenerate tree](https://www.geeksforgeeks.org/introduction-to-degenerate-binary-tree/)): $O(n)$`
	`197`	`+`
	`198`	`+> Where $n$ is the number of nodes in the treeand $h$ is the height of the tree.`
`195`	`199`
`196`	`200`	`---`
`197`	`201`

Comments

(0)