Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Sri Hari: Batch-5/Neetcode-250/Added-articles#3791

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.

Already on GitHub?Sign in to your account

Merged
neetcode-gh merged 2 commits intoneetcode-gh:mainfromSrihari2222:develop_articles
Jan 3, 2025
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
467 changes: 467 additions & 0 deletionsarticles/binary-tree-inorder-traversal.md
View file
Open in desktop

Large diffs are not rendered by default.

662 changes: 662 additions & 0 deletionsarticles/binary-tree-postorder-traversal.md
View file
Open in desktop

Large diffs are not rendered by default.

468 changes: 468 additions & 0 deletionsarticles/binary-tree-preorder-traversal.md
View file
Open in desktop

Large diffs are not rendered by default.

733 changes: 733 additions & 0 deletionsarticles/construct-quad-tree.md
View file
Open in desktop

Large diffs are not rendered by default.

577 changes: 577 additions & 0 deletionsarticles/delete-leaves-with-a-given-value.md
View file
Open in desktop

Large diffs are not rendered by default.

632 changes: 632 additions & 0 deletionsarticles/delete-node-in-a-bst.md
View file
Open in desktop

Large diffs are not rendered by default.

457 changes: 457 additions & 0 deletionsarticles/house-robber-iii.md
View file
Open in desktop

Large diffs are not rendered by default.

292 changes: 292 additions & 0 deletionsarticles/insert-into-a-binary-search-tree.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,292 @@
## 1. Recursion

::tabs-start

```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)

if val > root.val:
root.right = self.insertIntoBST(root.right, val)
else:
root.left = self.insertIntoBST(root.left, val)

return root
```

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}

if (val > root.val) {
root.right = insertIntoBST(root.right, val);
} else {
root.left = insertIntoBST(root.left, val);
}

return root;
}
}
```

```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) {
return new TreeNode(val);
}

if (val > root->val) {
root->right = insertIntoBST(root->right, val);
} else {
root->left = insertIntoBST(root->left, val);
}

return root;
}
};
```

```javascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
insertIntoBST(root, val) {
if (!root) {
return new TreeNode(val);
}

if (val > root.val) {
root.right = this.insertIntoBST(root.right, val);
} else {
root.left = this.insertIntoBST(root.left, val);
}

return root;
}
}
```

::tabs-end

### Time & Space Complexity

* Time complexity: $O(h)$
* Space complexity: $O(h)$ for the recursion stack.

> Where $h$ is the height of the given binary search tree.

---

## 2. Iteration

::tabs-start

```python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return TreeNode(val)

cur = root
while True:
if val > cur.val:
if not cur.right:
cur.right = TreeNode(val)
return root
cur = cur.right
else:
if not cur.left:
cur.left = TreeNode(val)
return root
cur = cur.left
```

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}

TreeNode cur = root;
while (true) {
if (val > cur.val) {
if (cur.right == null) {
cur.right = new TreeNode(val);
return root;
}
cur = cur.right;
} else {
if (cur.left == null) {
cur.left = new TreeNode(val);
return root;
}
cur = cur.left;
}
}
}
}
```

```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) {
return new TreeNode(val);
}

TreeNode* cur = root;
while (true) {
if (val > cur->val) {
if (!cur->right) {
cur->right = new TreeNode(val);
return root;
}
cur = cur->right;
} else {
if (!cur->left) {
cur->left = new TreeNode(val);
return root;
}
cur = cur->left;
}
}
}
};
```

```javascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* @param {TreeNode} root
* @param {number} val
* @return {TreeNode}
*/
insertIntoBST(root, val) {
if (!root) {
return new TreeNode(val);
}

let cur = root;
while (true) {
if (val > cur.val) {
if (!cur.right) {
cur.right = new TreeNode(val);
return root;
}
cur = cur.right;
} else {
if (!cur.left) {
cur.left = new TreeNode(val);
return root;
}
cur = cur.left;
}
}
}
}
```

::tabs-end

### Time & Space Complexity

* Time complexity: $O(h)$
* Space complexity: $O(1)$ extra space.

> Where $h$ is the height of the given binary search tree.
Loading
[8]ページ先頭
©2009-2025 Movatter.jp