{"id":8985,"date":"2025-08-06T00:14:30","date_gmt":"2025-08-05T18:44:30","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=8985"},"modified":"2025-08-06T00:14:31","modified_gmt":"2025-08-05T18:44:31","slug":"insert-into-a-bst","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/insert-into-a-bst\/","title":{"rendered":"Insert into a BST"},"content":{"rendered":"\n<!-- Validate Binary 1 -->\n<link\n    href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.min.css\"\n    rel=\"stylesheet\"\n\/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.min.js\"><\/script>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/plugins\/autoloader\/prism-autoloader.min.js\"><\/script>\n\n<style> \n.wp_blog_theme {\n  --primary: #E58C32;\n  --secondary: #f8c291;\n  --light-bg: #fef9f4;\n  --text-dark: #2d2d2d;\n  --tab-radius: 12px;\n  --shadow: 0 4px 12px rgba(0, 0, 0, 0.08);\n  --code-bg: #001f3f;\n  --code-text: #d4f1ff;\n}\n\n.wp_blog_container {\n  font-family: 'Segoe UI', sans-serif;\n  background: var(--light-bg);\n  margin: 0;\n  padding: 0;\n  color: var(--text-dark);\n}\n\n\/* Heading *\/\n.wp_blog_main-heading {\n  text-align: center;\n  font-size: 2.4rem;\n  color: var(--primary);\n  margin-top: 2.5rem;\n  font-weight: bold;\n}\n\n\/* Explanation Card *\/\n.wp_blog_explanation,\n.wp_blog_code-tabs-container {\n  max-width: 940px;\n  margin: 2rem auto;\n  padding: 2rem;\n  background: white;\n  border-radius: var(--tab-radius);\n  box-shadow: var(--shadow);\n}\n\n\/* Text and Visuals *\/\n.wp_blog_explanation h2{\n  font-size: 1.4rem;\n  color: var(--primary);\n  margin-bottom: 0.5rem;\n}\n.wp_blog_explanation h5{\n  color: var(--primary);\n}\n\n.wp_blog_explanation p,\n.wp_blog_explanation li {\n  font-size: 1.05rem;\n  line-height: 1.7;\n  margin: 0.5rem 0;\n}\n.wp_blog_explanation code {\n  background: #f9cea6;\n  color: #2d2d2d;\n  padding: 3px 6px;\n  border-radius: 4px;\n  font-family: 'Courier New', monospace;\n}\n.wp_blog_explanation img {\n  max-width: 100%;\n  border-radius: var(--tab-radius);\n  margin-top: 1rem;\n  box-shadow: 0 2px 12px rgba(0,0,0,0.06);\n}\n\n\/* Tab Buttons *\/\n.wp_blog_code-tabs-header {\n  display: flex;\n  flex-wrap: wrap;\n  gap: 0.5rem;\n  margin-bottom: 1rem;\n}\n.wp_blog_code-tab-button {\n  padding: 0.6rem 1.2rem;\n  border: 1px solid var(--primary);\n  background: white;\n  color: var(--primary);\n  border-radius: 50px;\n  font-weight: 600;\n  cursor: pointer;\n  transition: all 0.3s ease;\n}\n.wp_blog_code-tab-button:hover {\n  background: var(--secondary);\n}\n.wp_blog_code-tab-button.active {\n  background: var(--primary);\n  color: white;\n}\n\n\/* Code Content *\/\n.wp_blog_code-tab-content {\n  display: none;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n}\n.wp_blog_code-tab-content.active {\n  display: block;\n}\n.wp_blog_code-tab-content pre {\n  margin: 0;\n  padding: 1.5rem;\n  font-size: 1rem;\n  overflow-x: auto;\n  background: var(--code-bg);\n  border-radius: var(--tab-radius);\n  color: var(--code-text);\n}\n<\/style>\n\n<div class=\"wp_blog_container wp_blog_theme\"> \n    <h1 class=\"wp_blog_main-heading\"><\/h1>\n    <div class=\"wp_blog_explanation\">\n        <h2>Problem Statement:<\/h2>\n        <p>You are given the <code>root<\/code> node of a binary search tree (BST) and a <code>value<\/code> to insert into the tree. Return <i>the root node of the BST after the insertion<\/i>. It is <strong>guaranteed<\/strong> that the new value does not exist in the original BST.<\/p>\n        \n        <p><strong>Notice<\/strong> that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return <strong>any of them<\/strong>.<\/p>\n        <h2>Examples:<\/h2>\n                <h3>Example 1:<\/h3>\n                <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/08\/Screenshot-2025-08-05-at-11.55.57\u202fPM.png\" alt=\"\">\n                <p><strong>Input:<\/strong> root = [4,2,7,1,3], val = 5<\/p>\n                <p><strong>Output:<\/strong> [4,2,7,1,3,5]<\/p>\n                <p><strong>Explanation: <\/strong>Another accepted tree is:\n                <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/08\/Screenshot-2025-08-05-at-11.57.02\u202fPM.png\" alt=\"\">\n                <\/p>\n            \n                <h3>Example 2:<\/h3>\n                <p><strong>Input:<\/strong> root = [40,20,60,10,30,50,70], val = 25<\/p>\n                <p><strong>Output:<\/strong> [40,20,60,10,30,50,70,null,null,25]<\/p>\n\n                <h3>Example 3:<\/h3>\n                <p><strong>Input:<\/strong> root = [4,2,7,1,3,null,null,null,null,null,null], val = 5<\/p>\n                <p><strong>Output:<\/strong> [4,2,7,1,3,5]<\/p>\n\n                    <h2>Constraints:<\/h2>\n                    <ul>\n                        <li>The number of nodes in the tree will be in the range <code>[0, 10<sup>4<\/sup>]<\/code>.<\/li>\n                        <li><code>-10<sup>8<\/sup> <= Node.val <= 10<sup>8<\/sup><\/code><\/li>\n                        <li>All the values <code>Node.val<\/code> are <strong>unique.<\/strong><\/li>\n                        <li><code>-10<sup>8<\/sup> <= val <= 10<sup>8<\/sup><\/code><\/li>\n                        <li>It&#8217;s <strong>guaranteed<\/strong> that <code>val<\/code> does not exist in the original BST.<\/li>\n                    <\/ul>\n\n                <h2>Approach<\/h2>\n               <ul>\n                <li>If the current node (<code>root<\/code>) is <code>null<\/code>, create and return a new node with value <code>val<\/code>.<\/li>\n                <li>If <code>val<\/code> is greater than the current node&#8217;s value, recursively insert into the right subtree.<\/li>\n                <li>Otherwise, recursively insert into the left subtree.<\/li>\n                <li><strong>Return<\/strong> the unchanged root after insertion.<\/li>\n               <\/ul> \n\n                <h2>Time Complexity:<\/h2>\n                <li>\n                  <p><strong>Time Complexity = O(n)<\/strong>\n                  <\/li>\n                <h2>Space Complexity:<\/h2>\n                <li>\n                  <p><strong>Space Complexity = O(h)<\/strong>(h=tree height)<\/p>\n                <\/li>\n<h2>Dry Run<\/h2> <div style=\"background: #f9f9f9; padding: 10px; border: 1px solid #ccc; font-family: monospace;\"> <b>Function Call:<\/b> insertIntoBST(root, 1) where<br> root = Node(5)<br> \u251c\u2500\u2500 left: Node(3)<br> \u2502\u00a0\u00a0 \u251c\u2500\u2500 left: Node(2)<br> \u2502\u00a0\u00a0 \u2502\u00a0\u00a0 \u2514\u2500\u2500 left: null<br> \u2502\u00a0\u00a0 \u2502\u00a0\u00a0 \u2514\u2500\u2500 right: null<br> \u2502\u00a0\u00a0 \u2514\u2500\u2500 right: Node(4)<br> \u2514\u2500\u2500 right: Node(7)<br> &nbsp;&nbsp;&nbsp;&nbsp;\u251c\u2500\u2500 left: Node(6)<br> &nbsp;&nbsp;&nbsp;&nbsp;\u2514\u2500\u2500 right: Node(8)<br><br>\n<b>Step 1:<\/b><br>\n\u2192 insertIntoBST(curr = 5, val = 1)<br>\n\u2192 1 < 5 \u2192 go left<br>\n\u2192 insertIntoBST(curr = 3, val = 1)<br>\n\u2192 1 < 3 \u2192 go left<br>\n\u2192 insertIntoBST(curr = 2, val = 1)<br>\n\u2192 1 < 2 \u2192 go left<br>\n\u2192 insertIntoBST(curr = null, val = 1)<br>\n\u2192 return new TreeNode(1)<br><br>\n\u2192 Node(2).left = Node(1)<br>\n\u2192 return Node(2)<br>\n\u2192 Node(3).left = Node(2)<br>\n\u2192 return Node(3)<br>\n\u2192 Node(5).left = Node(3)<br>\n\u2192 return Node(5)<br><br>\n\n<b>Final Tree Structure:<\/b><br>\nroot = Node(5)<br>\n\u251c\u2500\u2500 left: Node(3)<br>\n\u2502\u00a0\u00a0 \u251c\u2500\u2500 left: Node(2)<br>\n\u2502\u00a0\u00a0 \u2502\u00a0\u00a0 \u2514\u2500\u2500 left: Node(1)<br>\n\u2502\u00a0\u00a0 \u2514\u2500\u2500 right: Node(4)<br>\n\u2514\u2500\u2500 right: Node(7)<br>\n\u00a0\u00a0\u00a0\u00a0\u251c\u2500\u2500 left: Node(6)<br>\n\u00a0\u00a0\u00a0\u00a0\u2514\u2500\u2500 right: Node(8)<br><br>\n\n<b>Final Result:<\/b> Node(5) \u2013 the tree with value 1 inserted at the correct position.\n\n<\/div>\n\n    <!-- <h2>Visualisation:<\/h2>\n        <img decoding=\"async\" src=\"https:\/\/namastedev.com\/blog\/wp-content\/uploads\/2025\/07\/Screenshot-2025-07-19-at-5.23.43\u202fPM.png\" alt=\"longest\" \/> -->\n    <\/div>\n    \n\n    <div class=\"wp_blog_code-tabs-container\">\n        <div class=\"wp_blog_code-tabs-header\">\n            <button class=\"wp_blog_code-tab-button active\" data-lang=\"js\">JavaScript<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"java\">Java<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"cpp\">C++<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"c\">C<\/button>\n            <button class=\"wp_blog_code-tab-button\" data-lang=\"cs\">C#<\/button>\n        <\/div>\n\n        <!-- JavaScript -->\n        <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n            <pre><code class=\"language-javascript\">\nvar insertIntoBST = function(root, val) {\n    if(!root) return new TreeNode(val);\n    if(root.val < val){\n        root.right = insertIntoBST(root.right, val);\n    }  else {\n        root.left = insertIntoBST(root.left, val);\n    }\n    return root;\n};\n  <\/code><\/pre>\n        <\/div>\n\n        <!-- Python -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n            <pre><code class=\"language-python\">\nclass TreeNode:\n    def __init__(self, val=0, left=None, right=None):\n        self.val = val\n        self.left = left\n        self.right = right\ndef insertIntoBST(root, val):\n    if not root:\n        return TreeNode(val)\n    if root.val < val:\n        root.right = insertIntoBST(root.right, val)\n    else:\n        root.left = insertIntoBST(root.left, val)\n    return root\n          <\/code><\/pre>\n        <\/div>\n\n        <!-- Java -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n            <pre><code class=\"language-java\">\nclass TreeNode {\n    int val;\n    TreeNode left, right;\n    \n    TreeNode(int x) {\n        val = x;\n        left = right = null;\n    }\n}\nclass Solution {\n    public TreeNode insertIntoBST(TreeNode root, int val) {\n        if (root == null) return new TreeNode(val);\n        if (root.val < val) {\n            root.right = insertIntoBST(root.right, val);\n        } else {\n            root.left = insertIntoBST(root.left, val);\n        }\n        return root;\n    }\n}\n     <\/code><\/pre>\n        <\/div>\n\n        <!-- C++ -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n            <pre><code class=\"language-cpp\">\nclass TreeNode {\npublic:\n    int val;\n    TreeNode *left, *right;\n    TreeNode(int x) : val(x), left(NULL), right(NULL) {}\n};\nTreeNode* insertIntoBST(TreeNode* root, int val) {\n    if (!root) return new TreeNode(val);\n    if (root->val < val) {\n        root->right = insertIntoBST(root->right, val);\n    } else {\n        root->left = insertIntoBST(root->left, val);\n    }\n    return root;\n}\n\n    <\/code><\/pre>\n        <\/div>\n\n        <!-- C -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n            <pre><code class=\"language-c\">\ntypedef struct TreeNode {\n    int val;\n    struct TreeNode *left;\n    struct TreeNode *right;\n} TreeNode;\n\nTreeNode* newNode(int val) {\n    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));\n    node->val = val;\n    node->left = node->right = NULL;\n    return node;\n}\nTreeNode* insertIntoBST(TreeNode* root, int val) {\n    if (root == NULL) return newNode(val);\n    if (root->val < val) {\n        root->right = insertIntoBST(root->right, val);\n    } else {\n        root->left = insertIntoBST(root->left, val);\n    }\n    return root;\n}\n            <\/code><\/pre>\n        <\/div>\n\n        <!-- C# -->\n        <div class=\"wp_blog_code-tab-content\" data-lang=\"cs\">\n            <pre><code class=\"language-csharp\">\npublic class TreeNode {\n    public int val;\n    public TreeNode left;\n    public TreeNode right;\n\n    public TreeNode(int val = 0) {\n        this.val = val;\n        this.left = null;\n        this.right = null;\n    }\n}\npublic class Solution {\n    public TreeNode InsertIntoBST(TreeNode root, int val) {\n        if (root == null) return new TreeNode(val);\n        if (root.val < val) {\n            root.right = InsertIntoBST(root.right, val);\n        } else {\n            root.left = InsertIntoBST(root.left, val);\n        }\n        return root;\n    }\n}\n            <\/code><\/pre>\n        <\/div>\n    <\/div>\n<\/div>\n\n<script>\n    document.addEventListener(\"DOMContentLoaded\", () => {\n        const buttons = document.querySelectorAll(\".wp_blog_code-tab-button\");\n        const contents = document.querySelectorAll(\".wp_blog_code-tab-content\");\n\n        buttons.forEach((button) => {\n            button.addEventListener(\"click\", () => {\n                const lang = button.getAttribute(\"data-lang\");\n\n                buttons.forEach((btn) => btn.classList.remove(\"active\"));\n                contents.forEach((content) =>\n                    content.classList.remove(\"active\")\n                );\n\n                button.classList.add(\"active\");\n                document\n                    .querySelector(`.wp_blog_code-tab-content[data-lang=\"${lang}\"]`)\n                    .classList.add(\"active\");\n            });\n        });\n    });\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>Problem Statement: You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST. Notice that there may exist multiple valid ways for<\/p>\n","protected":false},"author":108,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-8985","post","type-post","status-publish","format-standard","category-uncategorized"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8985","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/users\/108"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=8985"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8985\/revisions"}],"predecessor-version":[{"id":8986,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/8985\/revisions\/8986"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=8985"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=8985"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=8985"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}