{"id":10241,"date":"2025-10-13T10:55:37","date_gmt":"2025-10-13T05:25:37","guid":{"rendered":"https:\/\/namastedev.com\/blog\/?p=10241"},"modified":"2025-10-13T10:55:37","modified_gmt":"2025-10-13T05:25:37","slug":"insert-into-a-binary-search-tree","status":"publish","type":"post","link":"https:\/\/namastedev.com\/blog\/insert-into-a-binary-search-tree\/","title":{"rendered":"Insert into a Binary Search Tree"},"content":{"rendered":"\n<!-- Prism.js CSS and JS -->\n<link href=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/themes\/prism-tomorrow.css\" rel=\"stylesheet\" \/>\n<script src=\"https:\/\/cdn.jsdelivr.net\/npm\/prismjs@1.29.0\/prism.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_code-tabs-container {\n    font-family: \"Segoe UI\", sans-serif !important;\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    border: 1px solid #ddd !important;\n    border-radius: 8px !important;\n    overflow: hidden !important;\n    background-color: white !important;\n  }\n\n  .wp_blog_code-tabs-header {\n    background: #f7f7f7 !important;\n    display: flex !important;\n    border-bottom: 1px solid #ddd !important;\n  }\n\n  .wp_blog_code-tab-button {\n    flex: 1 !important;\n    padding: 10px 15px !important;\n    border: none !important;\n    background: transparent !important;\n    cursor: pointer !important;\n    font-weight: bold !important;\n    transition: background 0.2s !important;\n    color: #242b33 !important;\n  }\n\n  .wp_blog_code-tab-button.active {\n    background: white !important;\n    border-bottom: 3px solid #0073aa !important;\n  }\n\n  .wp_blog_code-tab-content {\n    display: none !important;\n    padding: 20px !important;\n    background: #242b33 !important;\n  }\n\n  .wp_blog_code-tab-content > pre {\n    background: #242b33 !important;\n  }\n\n  .wp_blog_code-tab-content.active {\n    display: block !important;\n  }\n\n  .wp_blog_code-tab-content pre {\n    margin: 0 !important;\n    overflow-x: auto !important;\n  }\n\n  .wp_blog_explanation {\n    max-width: 900px !important;\n    margin: 2rem auto !important;\n    font-family: \"Segoe UI\", sans-serif !important;\n    line-height: 1.6 !important;\n    background: white !important;\n    color: black !important;\n    padding: 1rem !important;\n    border-radius: 8px !important;\n  }\n\n  .wp_blog_explanation h2 {\n    color: #0073aa !important;\n    font-size: 1.5rem !important;\n    margin-bottom: 0.5rem !important;\n  }\n\n  .wp_blog_explanation code {\n    background: #f1f1f1 !important;\n    padding: 2px 6px !important;\n    border-radius: 4px !important;\n    font-family: monospace !important;\n  }\n\n  .wp_blog_explanation h1,\n  .wp_blog_explanation h2,\n  .wp_blog_explanation h3,\n  .wp_blog_explanation h4,\n  .wp_blog_explanation h5,\n  .wp_blog_explanation h6,\n  .wp_blog_explanation p {\n    margin-top: 10px !important;\n    margin-bottom: 10px !important;\n  }\n<\/style>\n\n<div class=\"wp_blog_explanation\">\n    <p>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.<\/p>\n    <p>It is guaranteed that the new value does not exist in the original BST.<\/p>\n    <p>There may be multiple valid insertion ways as long as the tree remains a valid BST.<\/p>\n  \n    <h2>Examples<\/h2>\n    <p><strong>Input:<\/strong> <code>root = [4,2,7,1,3], val = 5<\/code><\/p>\n    <p><strong>Output:<\/strong> <code>[4,2,7,1,3,5]<\/code><\/p>\n  \n    <p><strong>Input:<\/strong> <code>root = [40,20,60,10,30,50,70], val = 25<\/code><\/p>\n    <p><strong>Output:<\/strong> <code>[40,20,60,10,30,50,70,null,null,25]<\/code><\/p>\n  \n    <h2>Approach<\/h2>\n    <ul>\n      <li>Use recursion to find the correct insertion point.<\/li>\n      <li>If the node is <code>null<\/code>, create a new TreeNode and return it.<\/li>\n      <li>If <code>val &lt; root.val<\/code>, insert it into the left subtree.<\/li>\n      <li>If <code>val &gt; root.val<\/code>, insert it into the right subtree.<\/li>\n      <li>Return the root node to maintain the tree structure.<\/li>\n    <\/ul>\n  \n    <h2>Time &#038; Space Complexity<\/h2>\n    <ul>\n      <li><strong>Time Complexity:<\/strong> O(n), where h is the height of the tree<\/li>\n      <li><strong>Space Complexity:<\/strong> O(n) due to recursion<\/li>\n    <\/ul>\n  <\/div>\n  \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=\"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=\"java\">Java<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"py\">Python<\/button>\n      <button class=\"wp_blog_code-tab-button\" data-lang=\"c#\">C#<\/button>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content active\" data-lang=\"js\">\n      <pre><code class=\"language-javascript\">\n  var insertIntoBST = function(root, val) {\n      if (!root) return new TreeNode(val);\n  \n      if (root.val < val) {\n          root.right = insertIntoBST(root.right, val);\n      } else {\n          root.left = insertIntoBST(root.left, val);\n      }\n  \n      return root;\n  };\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"cpp\">\n      <pre><code class=\"language-cpp\">\n  struct TreeNode {\n      int val;\n      TreeNode* left;\n      TreeNode* right;\n      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n  };\n  \n  TreeNode* insertIntoBST(TreeNode* root, int val) {\n      if (!root) return new TreeNode(val);\n      if (val < root->val)\n          root->left = insertIntoBST(root->left, val);\n      else\n          root->right = insertIntoBST(root->right, val);\n      return root;\n  }\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c\">\n      <pre><code class=\"language-c\">\n  struct TreeNode {\n      int val;\n      struct TreeNode* left;\n      struct TreeNode* right;\n  };\n  \n  struct TreeNode* createNode(int val) {\n      struct TreeNode* node = malloc(sizeof(struct TreeNode));\n      node->val = val;\n      node->left = node->right = NULL;\n      return node;\n  }\n  \n  struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {\n      if (!root) return createNode(val);\n      if (val < root->val)\n          root->left = insertIntoBST(root->left, val);\n      else\n          root->right = insertIntoBST(root->right, val);\n      return root;\n  }\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"java\">\n      <pre><code class=\"language-java\">\n  class TreeNode {\n      int val;\n      TreeNode left, right;\n      TreeNode(int x) { val = x; }\n  }\n  \n  public class Solution {\n      public TreeNode insertIntoBST(TreeNode root, int val) {\n          if (root == null) return new TreeNode(val);\n          if (val < root.val)\n              root.left = insertIntoBST(root.left, val);\n          else\n              root.right = insertIntoBST(root.right, val);\n          return root;\n      }\n  }\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"py\">\n      <pre><code class=\"language-python\">\n  class TreeNode:\n      def __init__(self, val=0, left=None, right=None):\n          self.val = val\n          self.left = left\n          self.right = right\n  \n  def insertIntoBST(root, val):\n      if not root:\n          return TreeNode(val)\n      if val < root.val:\n          root.left = insertIntoBST(root.left, val)\n      else:\n          root.right = insertIntoBST(root.right, val)\n      return root\n      <\/code><\/pre>\n    <\/div>\n  \n    <div class=\"wp_blog_code-tab-content\" data-lang=\"c#\">\n      <pre><code class=\"language-csharp\">\n  public class TreeNode {\n      public int val;\n      public TreeNode left;\n      public TreeNode right;\n      public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n          this.val = val;\n          this.left = left;\n          this.right = right;\n      }\n  }\n  \n  public class Solution {\n      public TreeNode InsertIntoBST(TreeNode root, int val) {\n          if (root == null) return new TreeNode(val);\n          if (val < root.val)\n              root.left = InsertIntoBST(root.left, val);\n          else\n              root.right = InsertIntoBST(root.right, val);\n          return root;\n      }\n  }\n      <\/code><\/pre>\n    <\/div>\n  <\/div>\n  \n\n\n\n  <a href=\"https:\/\/leetcode.com\/problems\/insert-into-a-binary-search-tree\/description\/\" target=\"blank\">Solve this problem.<\/a>\n  <script>\n  document.addEventListener(\"DOMContentLoaded\", function () {\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        button.classList.add(\"active\");\n\n        contents.forEach((content) => {\n          content.classList.toggle(\"active\", content.getAttribute(\"data-lang\") === lang);\n        });\n      });\n    });\n  });\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>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. There may be multiple valid insertion ways as long as the<\/p>\n","protected":false},"author":1,"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":[811],"tags":[],"class_list":{"0":"post-10241","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-data-structures-and-algorithms"},"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10241","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\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/comments?post=10241"}],"version-history":[{"count":1,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10241\/revisions"}],"predecessor-version":[{"id":10242,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/posts\/10241\/revisions\/10242"}],"wp:attachment":[{"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/media?parent=10241"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/categories?post=10241"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/namastedev.com\/blog\/wp-json\/wp\/v2\/tags?post=10241"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}