Code_Craft__findMin.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNRb4TbpxQCR6zbaP4eb1Qu",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/walkerjian/DailyCode/blob/main/Code_Craft__findMin.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Problem:\n",
        "Given a node in a binary search tree, return the next bigger element, also known as the inorder successor.\n",
        "\n",
        "For example, the inorder successor of 22 is 30.\n",
        "```\n",
        "   10\n",
        "  /  \\\n",
        " 5    30\n",
        "     /  \\\n",
        "   22    35\n",
        "```\n",
        "You can assume each node has a parent pointer."
      ],
      "metadata": {
        "id": "1eKdaKQurqiL"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Solution:\n",
        "To find the inorder successor of a given node in a binary search tree (BST), there are two main cases to consider:\n",
        "\n",
        "1. **The node has a right subtree**: In this case, the inorder successor is the leftmost (minimum) node in its right subtree.\n",
        "2. **The node does not have a right subtree**: In this case, we go up the BST using the parent pointers until we find a node which is the left child of its parent. This parent node is the inorder successor.\n",
        "\n",
        "Here's a Python function to achieve this. The function assumes that each node in the BST has three properties: `value` (the node's value), `left` (the left child), `right` (the right child), and `parent` (the parent of the node).\n",
        "\n"
      ],
      "metadata": {
        "id": "41WAXXbprxWo"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 14,
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 551
        },
        "id": "PpvnaArQromH",
        "outputId": "abdad0b0-31d1-4b42-ec7c-110b45827097"
      },
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<Figure size 640x480 with 1 Axes>"
            ],
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAApQAAAHzCAYAAACe1o1DAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAAAspklEQVR4nO3de7TdBX3n/e/e55ZzyMkxIYFgLqWCISmk0AFCuUvtFEVFVDSGKqOj67Gj7Uwr+ljLjFh8pI4Pj/q0rufpeFkKCohgx0XBy0IQooRJqlUIloComAsEAuR2cpJz23v+CAmEc8k+57cvv8vr9V/IPvu3w1r5rU9++7ffu1StVqsBAADTVG71CwAAINsMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEjEoAQBIxKAEACARgxIAgEQMSgAAEmlv9QsApmZ4tBIbtu6O9Vt2xkNbdsbTuwdjaGQ0Otvb4qjerjhpQV8sX9AXS+f3RkebfzMC0HilarVabfWLAA5v8/aBuHHdxrhh7cbYuXc4IiLay6UYqbzwV/jFv+7r7og/PWNxXLZicSyc3dOS1wxAMRiUkHK79g3HNXc8HDf/ZFOUShGVKfyNLZciqhGx8tRFceXrlkXvjI6GvU4AisughBRb/ei2uOKWB+LZPYNTGpIvVS5FzJ3ZFddeenKct2Re/V4gAIRBCal13ZrH46p//kWUp3hVciIHnufqi0+My888NvkTAsDzDEpIoevvfzw+dtsvGvb8RiUA9eQjoJAyqx/d1tAxGRHxsdt+Easf3dbQYwBQHAYlpMiufcNxxS0PRLnU2OOUSxEfuvWB2L1vuLEHAqAQDEpIkWvueDjxB3BqUalGPNM/GJ/8zsONPRAAheAeSkiJTdsH4rxP/zBe+heyMrQ3dq39pxh84pEYevLRqOzrjyMv+suY+ft/POY5hp/ZFM/d9cUY3PxvUWprj+7jTo/Zr35vtPX0jXvMUiniRx++QKcSgERcoYSUuGndxiiN81Z3ZWBX7Lzvphh+dlN0HPW7E/78yK5nYusNH4mR7U/Gy86/PGateHPs/dW/xFPf+K9RHR3/re3y88cFgCQMSkiB4dFK3LB247hvdbfNnBML//xrsfD9X4nZF/zHCZ9j5/3fjOrwYBy96pMx67SLo++st8XcS/46hp/+TfSvv2vcnxmtRnx97cYYHq3U648CQAEZlJACG7buPvh1ii9Vau+ItpmzD/scA4+sie7jT4/2vqMO/rfuY0+J9jkLYuDhH034czv3DscjW3dP/UUDwPMMSkiB9Vt2Jvr5kd3PRGVgR3TOP37M73UdsySGnvp1Q48PQLEZlJACD23ZGe0JWkGj/dsjYv/b4y/VNnN2VPbtjurI+FdA28slgxKARAxKSIGndw/GSIJWUHVkMCIiSm0dY36v1NZ5yGNeaqRSjW394/8eANTCoIQUGBoZTfTzpfauiIhxP81dHR065DHjGRxOdnwAis2ghBTobG9L9PMHPrQz2v/cmN8b7d8e5Rm9UWofe/XygK6OZMcHoNgMSkiBo3q7Et1D2d47N8o9fTG09bExvzf45KPRefTE/cr2cinmzZz46iUAHI5BCSlw0oK+RPdQRkT0nHBW7H3sX2Jk17aD/23v4z+Pkee2RM/Scyb8uZFKNZYvGP+bdACgFu2tfgFAHHbQ7frpP0dl356Db2nvfWxdjOx+JiIiZp36hijPOCL6znxbDGy4L5668W+i97SLozq8/ysbO+YdGzOX//tExweAyRiUkAJL5/dGX3fHhHHzXWv/Z4zuevrgrwceXRPx6JqIiJh54gVRnnFEtM+aF0df9nex/e4vxY57vxqlcnt0H396zP6j90x6/2Rfd0ecML+3vn8gAAqlVK1Wk73PBtTFp7+/If7x3l+N+/WLjdJWiviz84+LD1+4tHkHBSB33EMJKXHZisXR7H/eVSJi1YrFzT0oALljUEJKLJzdEytPWxQJPuw9JeVSxMrTFsXC2T3NOSAAuWVQQopc+bplMXdmV8NHZbkUMXdmV1x50bLGHgiAQjAoIUV6Z3TEtZee3PD7KCvViGsvPTl6Z0z8YR0AqJVBCSlz7ivnxpJdP2voMT5x8Ylx3pJ5DT0GAMVhUELKfPzjH487/7//Fq+fPxARUbe3vw88z667vxivqGypz5MCQBiUkCpf+MIX4uqrr45PfepT8fn/8ta4/t0r6nJP5YF7Jr/8jj+I3+/eEW94wxtiw4YN9XnRABSeDiWkxO233x5vfOMb4/3vf3/8/d//fZRK+1fkrn3Dcc0dD8fNP90U5YgYncLf2LbS/jTQylMXxZWvWxa9Mzpix44dcc4550R/f3/cf//9ccwxxzTkzwNAcRiUkAJr166NCy64IF772tfGN7/5zWhraxvzmM3bB+KmdRvj62s3HvxGnfZy6ZDvAH/xr/u6O+IdZyyOVSsWj0kDbd68Oc4888yYO3du3HvvvTFr1qwG/ukAyDuDElrsl7/8ZZx11llxwgknxJ133hnd3d2TPn54tBKPbN0d67fsjPVbdsa2/sEYHB6Nro62mDezK5Yv6IvlC/rihPm90dE28V0tDz30UJxzzjlx+umnxx133BGdnZ31/qMBUBAGJbTQU089FWeddVZ0dnbGfffdF3PmzGnq8e+555648MILY+XKlXHdddcdfJsdAKbCh3KgRfr7++P1r3997N27N773ve81fUxGRLzqVa+K66+/Pr72ta/FlVde2fTjA5AP7a1+AVBEw8PD8ba3vS0eeeSRWL16dfzO7/xOy17LypUr44knnogPfvCDsWDBgvjABz7QstcCQDYZlNBk1Wo13ve+98Wdd94Z3/3ud+OUU05p9UuKv/qrv4pNmzbFX/zFX8TLX/7yeNOb3tTqlwRAhriHEprsqquuiquvvjq+9rWvxTve8Y5Wv5yDKpVKrFq1Km677bb4wQ9+EGeffXarXxIAGWFQQhN94QtfiPe9733xqU99Kj7ykY+0+uWMMTg4GBdeeGE8+OCDsWbNmli6dGmrXxIAGWBQQpNMFC5PG+FzAKbKoIQmqCVcnibC5wBMhUEJDTbVcHlaCJ8DUCuDEhqo1eHypITPAaiFsDk0SBrC5UkJnwNQCx1KaIA0hcuTEj4H4HAMSqizNIbLkxI+B2Ay7qGEOktruDwp4XMAJmJQQh2lPVyelPA5AOMxKKFOshIuT0r4HICXMiihDrIWLk9K+ByAFzMoIaGshsuTEj4H4ACDEhLIerg8KeFzACKEzWHa8hAuT0r4HIAIHUqYljyFy5MSPgfAoIQpymO4PCnhc4Bicw8lTFFew+VJCZ8DFJdBCVOQ93B5UsLnAMVkUEKNihIuT0r4HKB4DEqoQdHC5UkJnwMUi0EJh1HUcHlSwucAxWFQwiSKHi5PSvgcoBiEzWECwuXJCZ8DFIMOJYxDuLx+hM8B8s+ghJcQLq8/4XOAfHMPJbyEcHljCJ8D5JdBCS8iXN5YwucA+WRQwvOEy5tD+BwgfwxKCOHyZhM+B8gXg5LCEy5vDeFzgPwwKCk04fLWEj4HyAdhcwpLuLz1hM8B8kGHkkISLk8P4XOA7DMoKRzh8vQRPgfINvdQUjjC5ekkfA6QXQYlhSJcnm7C5wDZZFBSGMLl2SB8DpA9BiWFIFyeLcLnANliUJJ7wuXZJHwOkB0GJbkmXJ5twucA2SBsTm4Jl2ef8DlANuhQkkvC5fkhfA6QfgYluSNcnj/C5wDp5h5Kcke4PJ+EzwHSy6AkV4TL8034HCCdDEpyQ7i8GITPAdLHoCQXhMuLRfgcIF0MSjJPuLyYhM8B0sOgJNOEy4tN+BwgHYTNySzhcoTPAdJBh5JMEi7nAOFzgNYzKMkc4XJeSvgcoLXcQ0nmCJczHuFzgNYxKMkU4XImI3wO0BoGJZkhXE4thM8Bms+gJBOEy5kK4XOA5jIoST3hcqZD+BygeQxKUk24nCSEzwGaQ9ic1BIuJynhc4Dm0KEklYTLqRfhc4DGMyhJHeFy6k34HKCx3ENJ6giX0wjC5wCNY1CSKsLlNJLwOUBjGJSkhnA5zSB8DlB/BiWpIFxOMwmfA9SXQUnLCZfTCsLnAPVjUNJSwuW0kvA5QH0Im9MywuW0mvA5QH3oUNISwuWkhfA5QHIGJU0nXE7aCJ8DJOMeSppOuJw0Ej4HmD6DkqYSLifNhM8BpsegpGmEy8kC4XOAqTMoaQrhcrJE+BxgagxKGk64nCwSPgeonUFJQwmXk2XC5wC1ETanYYTLyTrhc4Da6FDSEMLl5IXwOcDhGZTUnXA5eSN8DjA591BSd8Ll5JHwOcDEDErqSricPBM+BxifQUndCJdTBMLnAGMZlNSFcDlFInwOcCiDksSEyyki4XOAFxiUJCJcTpEJnwPsJ2zOtAmXU3TC5wD76VAyLcLlsJ/wOYBByTQIl8OhhM+BonMPJVMmXA5jCZ8DRWZQMiXC5TAx4XOgqAxKaiZcDocnfA4UkUFJTYTLoXbC50DRGJQclnA5TJ3wOVAkBiWTEi6H6RM+B4pC2JwJCZdDMsLnQFHoUDIu4XKoD+FzoAgMSsYQLof6Ej4H8s49lIwhXA71J3wO5JlBySGEy6FxhM+BvDIoOUi4HBpP+BzII4OSiBAuh2YSPgfyxqBEuBxaQPgcyBODsuCEy6F1hM+BvBA2LzDhcmgt4XMgL3QoC0q4HNJB+BzIA4OygITLIV2Ez4Gscw9lAQmXQ/oInwNZZlAWjHA5pJfwOZBVBmWBCJdD+gmfA1lkUBaEcDlkh/A5kDUGZQEIl0P2CJ8DWWJQ5pxwOWSX8DmQFcLmOSZcDtkmfA5khQ5lTgmXQz4InwNZYFDmkHA55IvwOZB27qHMIeFyyB/hcyDNDMqcES6H/BI+B9LKoMwR4XLIP+FzII0MypwQLofiED4H0sagzAHhcige4XMgTQzKjBMuh+ISPgfSQtg8w4TLodiEz4G00KHMKOFyIEL4HEgHgzKDhMuBFxM+B1rNPZQZJFwOvJTwOdBKBmXGCJcDExE+B1rFoMwQ4XLgcITPgVYwKDNCuByolfA50GwGZQYIlwNTJXwONJNBmXLC5cB0CZ8DzSJsnmLC5UASwudAs+hQppRwOVAPwudAMxiUKSRcDtST8DnQaO6hTCHhcqDehM+BRjIoU0a4HGgU4XOgUQzKFBEuBxpN+BxoBIMyJYTLgWYRPgfqzaBMAeFyoNmEz4F6MihbTLgcaBXhc6BehM1bSLgcaCXhc6BedChbRLgcSAPhc6AeDMoWEC4H0kT4HEjKPZQtIFwOpI3wOZCEQdlkwuVAWgmfA9NlUDaRcDmQdsLnwHQYlE0iXA5khfA5MFUGZRMIlwNZI3wOTIVB2WDC5UBWCZ8DtRI2byDhciDLhM+BWulQNohwOZAHwudALQzKBhAuB/JE+Bw4HPdQNoBwOZA3wufAZAzKOhMuB/JK+ByYiEFZR8LlQN4JnwPjMSjrRLgcKArhc+ClDMo6EC4Hikb4HHgxgzIh4XKgqITPgQOEzRMQLgeKTPgcOECHcpqEywGEz4H9Cjkoh0crsWHr7li/ZWc8tGVnPL17MIZGRqOzvS2O6u2Kkxb0xfIFfbF0fm90tI29iCtcDvCCqYTPk55/gXQq1D2Um7cPxI3rNsYNazfGzr3DERHRXi7FSOWF/wUv/nVfd0f86RmL47IVi2Ph7J6DjxEuBzjU4cLn9Tr/AulUiEG5a99wXHPHw3HzTzZFqRRRmcKfuFyKqEbEylMXxZWvWxY3Xf8V4XKAcYwXPq/n+bd3RkfDXjuQTO4H5epHt8UVtzwQz+4ZnNKJ7KXKpYiZ7dV47Iar4j0XnSVcDjCOF4fPP/eN78cn79pUl/Pv3Jldce2lJ8d5S+bV78UCdZPrQXndmsfjqn/+RZSn+K/iiVQro1Eqt8XHX78s3nX2K5I/IUAObd68Oc76Dx+N8oq31+38e+B5rr74xLj8zGOTPyFQV7m94/n6+/ePyYj6nMwiIkrl/d9+8/HbH47r73+8Pk8KkDN3bxqJ8oq3R0T9zr8Hnudjt/3C+RdSKJdXKFc/ui0u/8q6hh/n+nev8PYLwIs4/0Ix5e4K5a59w3HFLQ9EucG3N5ZLER+69YHYvW+4sQcCyAjnXyiu3A3Ka+54OPEN4LWoVCOe6R+MT37n4cYeCCAjnH+huHL1lvem7QNx3qd/GLX8gfb99sF46qa/Gff35r/z2uhasLSmY5ZKET/68AU6aUChTXT+Hdr229j54xtjaOtjMbpnR5Q6uqLjyEUx64w3R88rzzjkscPPbIrn7vpiDG7+tyi1tUf3cafH7Fe/N9p6+sY9pvMvpEeuvinnpnUbo1SKmMpE7j31DdF5zJJD/lv77GNq/vny88f98IW1DVCAPJro/Du66+moDO2NI5a/Otpmzonq8GAMPLImtn3rEzHnNX8evae8JiIiRnY9E1tv+EiUu46Il51/eVSH9sWudf8UQ9sej2P+w2ei1Da2Qen8C+mRm0E5PFqJG9ZunPJbLV2LTowjlp4z7eOOViO+vnZj/OUfL/E1YUAhTXb+7T7u9Og+7vRD/lvvqa+PJ7/6l7Fr3bcPDsqd938zqsODcfS7PhftfUdFRETny5fE09/4r9G//q6Dj3sx519Ij9z8DdywdffBr/OaqsrgQFQro9M+9s69w/HI1t3T/nmALJvq+bdUbov23rlRGew/+N8GHlkT3ceffnBMRkR0H3tKtM9ZEAMP/2jC53L+hXTIzRXK9Vt2Tuvnnv3O/xvVob0RpXJ0LToxZl/wH6PrmFdO6/gnLRj/Ph+APKvl/FsZ2hfVkcGoDA7E3l+ujb2//mn0LDs3IiJGdj8TlYEd0Tn/+DE/13XMktj7q58c9vjOv9BauRmUD23ZGe3lUozU+p53W0f0nHBWdL/itCj39MXwMxtj17r/GU/d8JGY/47/OzrnH1fzsdvLpVi/ZWesmuZrB8iyWs6/2+/+UvT//Hv7f1EqR8+SM2POn/yniIgY7d8eERFtM+eM+bm2mbOjsm93VEeGo9Q+9j5K519Ih9wMyqd3D9Y+JiNixsJlMWPhshf+wyvPiJ6lZ8eTX/6L2H7vdXH0yqtrfq6RSjW29Q9O5eUC5EYt599Zp78xepaeE6O7n42BDT+OarUSMbr/bfLqyP7z53gfvCm1dR58zHiD0vkX0iE391AOjUz/HsgDOma/PLpfeUbs2/jglO+pHBxOfnyALKrl/Ntx5KLoPvaUmLn81XHUW6+K6tC+ePrWq6NarUapvSsiIqqjY+/DrI4ORUQcfMx4nH+h9XIzKDvb2+ryPO2z5kaMjkR1eGr/4u3qqM/xAbJmOuffnqVnx9CTv4yR57ZE28zZEREx2v/cmMeN9m+P8ozeca9OHuD8C62Xm0F5VG9XtNfh+75GdmyNUntnlDpn1Pwz7eVSzJs58b+eAfJsOuffA/9orwzuifbeuVHu6YuhrY+Nedzgk49G59G/O+HzOP9COuRmUJ60oG9K91CODoz9VOLQU7+OgV+uixnH/kGUSrX/rxmpVGO5TxgCBTXZ+Xd0z44x/606OhJ7Hro7Su1d0TF3cURE9JxwVux97F9iZNe2g4/b+/jPY+S5LdEzSSvY+RfSITcfypnqCWXbt/97lDs6o2vBsuc/5b0p+h/4XpQ6umL2q97V8OMD5MVk579nv/f5qA4NRNeik6Kt98gY7d8ee/7tnhh5dnPM/qP3RLmzOyIi+s58WwxsuC+euvFvove0i6M6vDd2rf2n6Jh3bMxc/u+nfXygOXIzKJfO742+7o6a47o9S/4w9vzinti17ttRGRqItp6+6FlyVvSdsyo6Zr98Ssfu6+6IE+b3TudlA2TeZOffI5adG/0P3hm7f/adqOzdHeXO7uicf3zMftW7D/ku7/ZZ8+Loy/4utt/9pdhx71ejVG6P7uNPj9l/9J5J7590/oV0KFWrU/nm63T79Pc3xD/e+6spf/1iEm2liD87/zjfJQsUmvMvFFtu7qGMiLhsxeJo9jyuRMSqFYube1CAlHH+hWLL1aBcOLsnVp62KOrwYe+alEsRK09bFAtn9zTngAAp5fwLxZarQRkRceXrlsXcmV0NP6mVSxFzZ3bFlRctO/yDAQrA+ReKK3eDsndGR1x76ckNv4+nUo249tKTo3fGxDeLAxSJ8y8UV+4GZUTEeUvmxdUXn9jQY3zi4hPjvCXzGnoMgKw5b8m8+Ktzp1bKmCrnX0ifXA7KiIjLzzz24Kis19svB57nExefGO8889j6PClAjuzYsSO++H++M+InN0dE/c+/u+7+YryisqU+TwrUTW4HZcT+UXn9u1fU5Z6eA/fsXP/uFcYkwDgGBwfjkksuiSeffDK+9w9/U/fz75ff8Qfx+9074g1veENs2LChPi8aqItcdSgnsmvfcFxzx8Nx8083RTkiRqfwJ24r7U9TrDx1UVz5umXu2QEYR6VSiVWrVsVtt90WP/jBD+Lss8+OiPqff3fs2BHnnHNO9Pf3x/333x/HHHNMQ/48wNQUYlAesHn7QNy0bmN8fe3Gg9/o0F4uHfIdtC/+dV93R7zjjMWxasViaQqASXzwgx+Mz33uc/Gtb30r3vSmN435/Xqefzdt2hRnnnlmzJs3L+69996YNWtWA/9kQC0KNSgPGB6txCNbd8f6LTtj/Zadsa1/MAaHR6Oroy3mzeyK5Qv6YvmCvjhhfm90tOX6rgCAxD7zmc/EFVdcEZ///OfjAx/4wKSPrdf5d/369XHuuefG6aefHnfccUd0dnbW+48FTEEhByUA9XHzzTfH29/+9vjoRz8a11xzTVOPfc8998SFF14YK1eujOuuuy5KpSZV1YExDEoApiUNg66VgxZ4QXurXwAA2bN+/fq45JJL4vzzz48vfelLLbs6uHLlynjiiSfigx/8YCxcuDDe//73t+R1QNG5QgnAlLz4QzGrV6+O3t7eVr+kw34oCGgsgxKAmqU12zNRtghoDoMSgJoMDg7GhRdeGOvXr4/77rsvli5d2uqXdIgDr+/BBx+MNWvWpO71QZ4ZlAAcVlauAKb1CirkncgiAIf1oQ99KG655Za48cYbUzsmIyJe9rKXxXe/+90YGRmJiy66KHbt2tXqlwSFYFACMKnPfOYz8dnPfjb+4R/+IRMfeFm0aFF897vfjd/85jfxlre8JYaGhlr9kiD3DEoAJnTzzTfHFVdcER/96EcP+y04abJ8+fL49re/HatXr473vve94e4uaCz3UAIwrjSEy5MSPofmEDYHYIy0hMuTEj6H5nCFEoBDpDFcnpTwOTSWQQnAQXnN7mQlewRZZVACEBHpD5cnJXwOjWNQAlCYK3h5vQILrSYbBEBmwuVJCZ9DYxiUAAWXtXB5UsLnUH8GJUCBZTVcnpTwOdSXeygBCioP4fKkhM+hPoTNAQooL+HypITPoT5coQQomDyGy5MSPodkDEqAApHNGV9RsknQKAYlQEHkPVyelPA5TJ9BCVAArsDVxhVcmB7ZIIACKEq4PCnhc5gegxIg54oWLk9K+BymzqAEyLGihsuTEj6HqXEPJUBOCZcnJ3wOtRE2B8gh4fL6ED6H2rhCCZAzwuX1J3wOkzMoAXJE9qYxZJdgcgYlQE4IlzeW8DlMzKAEyAFX0JrDFWAYn2wQQA4IlzeH8DmMz6AEyDjh8uYSPoexDEqADBMubw3hcziUeygBMkq4vPWEz2E/YXOADBIuTwfhc9jPFUqAjBEuTx/hc4rOoATIENmadJJtougMSoCMEC5PN+FzisygBMgAV8CywRVkiko2CCADhMuzQficojIoAVJOuDxbhM8pIoMSIMWEy7NJ+JyicQ8lQEoJl2ef8DlFIWwOkELC5fkgfE5RuEIJkDLC5fkjfE7eGZQAKSI7k0+yT+SdQQmQEsLl+SZ8Tp4ZlAAp4ApWMbgCTV7JBgGkgHB5MQifk1cGJUCLCZcXi/A5eWRQArSQcHkxCZ+TN+6hBGgR4XKEz8kLYXOAFhAuJ0L4nPxwhRKgyYTLeSnhc7LOoARoItkYxiMbRdYZlABNIlzOZITPyTKDEqAJXIGiFq5gk1WyQQBNIFxOLYTPySqDEqDBhMuZCuFzssigBGgg4XKmQ/icrHEPJUCDCJeTlPA5WSFsDtAAwuXUg/A5WeEKJUCdCZdTb8LnpJ1BCVBHsi80guwUaWdQAtSJcDmNJHxOmhmUAHXgChLN4Ao4aSUbBFAHwuU0g/A5aWVQAiQkXE4zCZ+TRgYlQALC5bSC8Dlp4x5KgGkSLqfVhM9JC2FzgGkQLicNhM9JC1coAaZIuJy0ET6n1QxKgCmQbSGNZKtoNYMSoEbC5aSZ8DmtZFAC1MAVILLAFXRaRTYIoAbC5WSB8DmtYlACHIZwOVkifE4rGJQAkxAuJ4uEz2k291ACTEC4nKwTPqdZhM0BxiFcTh4In9MsrlACvIRwOXkjfE6jGZQALyK7Qh7JXtFoBiXA84TLyTPhcxrJoAQIV3AoBlfgaRTZIIAQLqcYhM9pFIMSKDzhcopE+JxGMCiBQhMup4iEz6k391AChSVcTtEJn1MvwuZAIQmXg/A59eMKJVA4wuVwKOFzkjIogUKRTYGxZLNIyqAECkO4HCYmfE4SBiVQCK7AwOG5gs90yQYBhSBcDocnfM50GZRA7gmXQ+2Ez5kOgxLINeFymDrhc6bKPZRAbgmXQzLC59RK2BzIJeFySE74nFq5QgnkjnA51JfwOYdjUAK5InsC9Se7xeEYlEBuCJdD4wifMxmDEsgFV1Cg8bwDwERkg4BcEC6HxhM+ZyIGJZB5wuXQPMLnjMegBDJNuByaT/icl3IPJZBZwuXQWsLnHCBsDmSScDm0nvA5B7hCCWSOcDmki/A5BiWQKbIlkD6yXRiUQGYIl0N6CZ8Xm0EJZIIrIJB+3kEoLtkgIBOEyyH9hM+Ly6AEUk+4HLJD+LyYDEog1YTLIXuEz4vHPZRAagmXQ7YJnxeHsDmQSsLlkH3C58XhCiWQOsLlkC/C5/lnUAKpIjsC+SP7lX8GJZAawuWQX8Ln+WZQAqngCgbkn3cg8ks2CEgF4XLIP+Hz/DIogZYTLofiED7PJ4MSaCnhcige4fP8cQ8l0DLC5VBswuf5IWwOtIRwOSB8nh+uUAJNJ1wOvJjwefYZlEBTyYYALyUbln0GJdA0wuXARITPs82gBJrCFQjgcLyDkV2yQUBTCJcDhyN8nl0GJdBwwuVArYTPs8mgBBpKuByYKuHz7HEPJdAwwuVAEsLn2SFsDjSEcDmQlPB5drhCCdSdcDlQT8Ln6WdQAnUl+wHUm+xY+hmUQN0IlwONInyebgYlUBeuIACN5h2Q9JINAupCuBxoNOHz9DIogcSEy4FmET5PJ4MSSES4HGg24fP0cQ8lMG3C5UArCZ+nh7A5MC3C5UCrCZ+nhyuUwJQJlwNpInzeegYlMCWyHUDayJa1nkEJ1Ey4HEgr4fPWMiiBmrgCAKSdd1BaRzYIqIlwOZB2wuetY1AChyVcDmSF8HlrGJTApITLgawRPm8+91ACExIuB7JM+Lx5hM2BcQmXA1knfN48rlACYwiXA3kifN54BiVwCNkNIG9kzxrPoAQOEi4H8kr4vLEMSiAi/AseyD/vwDSObBAQEcLlQP4JnzeOQQkIlwOFIXzeGAYlFJxwOVA0wuf15x5KKDDhcqDIhM/rR9gcCkq4HCg64fP6cYUSMmZ4tBIbtu6O9Vt2xkNbdsbTuwdjaGQ0Otvb4qjerjhpQV8sX9AXS+f3Rkfb+He1CJcDvKDW8Hk9zr95ZVBCRmzePhA3rtsYN6zdGDv3DkdERHu5FCOVF/4Kv/jXfd0d8adnLI7LViyOhbN7Dj5GNgPgUIfLptXr/JtnBiWk3K59w3HNHQ/HzT/ZFKVSRGUKf2PLpYhqRKw8dVFc+bpl0VmqCJcDjGO88Hk9z7+9Mzoa9trTwKCEFFv96La44pYH4tk9g1M6kb1UuRQxd2ZXzH709lh98/8QLgcYx4vfwfncN74fn7xrU93Ov9deenKct2Re/V5syhiUkFLXrXk8rvrnX0R5iv8qnlC1GlEqxVt+ZyT+nz97Yx2eECB/Nm3aFGe966PRtmJV3c6/B57n6otPjMvPPDb5E6ZQse4YhYy4/v79YzKiTmMyIuL5T3F/67ftcf39j9fpSQHy5YebR6NtxaqIqN/598DzfOy2X+T2/OsKJaTM6ke3xeVfWdfw41z/7hW5fvsFYKqcf6fPFUpIkV37huOKWx6IcoOTkOVSxIdufSB27xtu7IEAMsL5NxmDElLkmjseTnwDeC0q1Yhn+gfjk995uLEHAsgI599kvOUNKbFp+0Cc9+kfxov/Qg4++WjsWX9X7Nu4PkZ2PhXl7lnR9fIT4mXnvTM65iyIiIhqtRJ71t8dA4+uiaGnfh2Vfbujve/o6Fl2XvSd8eYotXdOeMxSKeJHH76gMJ00gPGMd/6NiBja9tvY+eMbY2jrYzG6Z0eUOrqi48hFMeuMN0fPK884+Lhnbv9s7HnorjHP2z5nYSz4P/5x3GPm7fzrqxchJW5atzFKpf0fxj5g1/+6NQY3Pxw9S8+JjqOOjdH+7bH7X2+PJ7/yX2L+5ddG57xjozo8GM9+53PR+fITovcPXhvlnr4Y3LIhdv74xtj32wfi6FXXTPi1iuXnj/vhC/UogeIa7/wbETG66+moDO2NI5a/Otpmzonq8GAMPLImtn3rEzHnNX8evae85oUHt3XEka/9z4f8fLlr4rGYt/OvK5SQAsOjlTjtkz84+A0MB+zb/HB0HXN8lNpeCOIOP7clnvjyn8cRS8+OuW/4UFRHh2PwycdixsJlh/zsjh/fFDt/fEMc9fb/K7qPPWXCY/d1d8RPrvzjwn1NGEDExOffiVQro/HkV/8yqiPDB68+PnP7Z2Pgkfti8RW3TunYeTr/Zv9PADmwYevucU9mMxYuO2RMRkR0zFkQnXMXx/AzmyIiotTWMWZMRkT0LDkzIuLg4yayc+9wPLJ193RfOkCmTXT+nUip3BbtvXOjMtg/5veqldGoDA7U/Fx5Ov96yxtSYP2WnTU/tlqtxujAjuiYu3jSx43u2R4REW09s2o6/kkL+mp+DQB5Ucv5tzK0L6ojg1EZHIi9v1wbe3/90+hZdu4hj6kOD8amz74tqsODUZ4xM3p+7/yY/ap3Rbmz+7DHz8P516CEFHhoy85oL5dipIaPF+75xT0xuvvZeNk5fzrp43at/VaUunqi+xWnTvq49nIp1m/ZGaum9IoB8qGW8+/2u78U/T//3v5flMrRs+TMmPMn/+ng77fNnB2z/vAt0Xn0cRHVSuz99b9G/7/eEcNP/yaOvuzvolRuG/d583T+NSghBZ7ePVjTmBx+dlM8d+f/H10LlsYRy1894eN2rvlm7Hv85zHnT94f5RkzJ33OkUo1tvUPTvk1A+RBLeffWae/MXqWnhOju5+NgQ0/jmq1EjH6wtvks1/1rkMef8TvnR8dcxbEjtXXx8CGH8cRv3f+uM+bp/OveyghBYZGRg/7mNH+7fH0LX8b5a4jYu4lH53wX7x7Hl4dO1Z/LWb+/p9E77+7qKbjDw4f/vgAeVTL+bfjyEXRfewpMXP5q+Oot14V1aF98fStV8dkn2vuPf2NEaVy7Hv8gUmfOy/nX4MSUqCzffxxeEBl35546ptXRWXfnjjqbX8b7b1Hjvu4vb/5WTxz+2ei+7jTYs5rPlDz8bs6Jj8+QF4d7vw7np6lZ8fQk7+Mkee2TPiYckdXlLt7Y3Tf5B+6ycv516CEFDiqtyvaJ/i+r+rIUDx969Uxsn1LHPXWj0XnBB/GGXzikdj2T5+MrvmvjLmX/PWEVzBfqr1cinkzu6b92gGybLLz70Sqw/vfpq4M7pnwMZXBgagM7Iq2nok/cJOn869BCSlw0oK+ce/hqVZGY9u3/3sMPrEh5l3y19G1YGweKGJ/GujpW/422vuOinlvvSrKHbWfoEYq1Vieg08YAkzHROffiIjRPTvG/Lfq6EjseejuKLV3RcfcxVEdGRo3FbRzzTciohrdv/vvJjx2ns6/PpQDKTDRCWX73V+OvY+tje7jV8To3v7of+iHh/z+zJMuiMrgQDz1zY9FZV9/zDrjzbH3sX855DEds+dPOEQPd3yAvJvs/Pfs9z4f1aGB6Fp0UrT1Hhmj/dtjz7/dEyPPbo7Zf/SeKHd2x8iOp+LJr/zn6Pm986PjyIUREbHvN/8ae3/1k5jxilOje8kfTvv4WWJQQgosnd8bfd0dY+K6Q0/9OiIi9j62LvY+tm7Mz8086YKo7N0do7u2RUTEjnu+OuYxR5z06kkHZV93R5wwvzfBqwfIronOvxERRyw7N/ofvDN2/+w7Udm7O8qd3dE5//iY/ap3H/wu7/KMI6L7+BWx7/GfxZ6H7opqpRIds4+Jl51/ecxa8eYolSZ+MzhP519fvQgp8envb4h/vPdXUUM9qG7aShF/dv5xufkuWYDpcP5Nzj2UkBKXrVgczf7nXSUiVq2Y/Bt3APLO+Tc5gxJSYuHsnlh52qKY4ocNp61cilh52qJYOLunOQcESCnn3+QMSkiRK1+3LObO7Gr4Sa1cipg7syuuvGjyD+sAFIXzbzIGJaRI74yOuPbSkxt+H0+lGnHtpSdH74yOxh4IICOcf5MxKCFlzlsyL66++MSGHuMTF58Y5y2Z19BjAGSN8+/0GZSQQpefeezBk1q93n458DyfuPjEeOeZx9bnSQFyxvl3emSDIMVWP7otPnTrA/FM/2Cit2EO3LNz7aUn5/JfxgD15vw7NQYlpNyufcNxzR0Px80/3RTliBidwt/YttL+NMXKUxfFla9blrt7dgAayfm3dgYlZMTm7QNx07qN8fW1Gw9+o0N7uXTId9C++Nd93R3xjjMWx6oVi3OVpgBoNuffwzMoIWOGRyvxyNbdsX7Lzli/ZWds6x+MweHR6Opoi3kzu2L5gr5YvqAvTpjfGx1tbpMGqBfn34kZlAAAJFKs+QwAQN0ZlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJGJQAgCQiEEJAEAiBiUAAIkYlAAAJPK/AWTPQ2GoCnP8AAAAAElFTkSuQmCC\n"
          },
          "metadata": {}
        },
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Inorder successor of node with value 22 is: 30\n",
            "Inorder successor of node with value 5 is: 10\n"
          ]
        }
      ],
      "source": [
        "import matplotlib.pyplot as plt\n",
        "import networkx as nx\n",
        "\n",
        "class TreeNode:\n",
        "    def __init__(self, value, left=None, right=None, parent=None):\n",
        "        self.value = value\n",
        "        self.left = left\n",
        "        self.right = right\n",
        "        self.parent = parent\n",
        "\n",
        "def findMin(node):\n",
        "    current = node\n",
        "    while current.left is not None:\n",
        "        current = current.left\n",
        "    return current\n",
        "\n",
        "def inorderSuccessor(node):\n",
        "    if node is None:\n",
        "        return None\n",
        "\n",
        "    # Case 1: Node has right subtree\n",
        "    if node.right:\n",
        "        return findMin(node.right)\n",
        "\n",
        "    # Case 2: Node has no right subtree\n",
        "    p = node.parent\n",
        "    while p is not None and node == p.right:\n",
        "        node = p\n",
        "        p = p.parent\n",
        "\n",
        "    return p\n",
        "\n",
        "def addNode(parent, child_value, is_left):\n",
        "    if parent is None:\n",
        "        return None\n",
        "\n",
        "    child = TreeNode(child_value, parent=parent)\n",
        "    if is_left:\n",
        "        parent.left = child\n",
        "    else:\n",
        "        parent.right = child\n",
        "    return child\n",
        "\n",
        "def drawTree(root):\n",
        "    if root is None:\n",
        "        return\n",
        "\n",
        "    def add_edges(node, G=None, pos=None, level=0, x=0):\n",
        "        if G is None:\n",
        "            G = nx.DiGraph()\n",
        "        if pos is None:\n",
        "            pos = {}\n",
        "\n",
        "        pos[node.value] = (x, -level)\n",
        "        if node.left:\n",
        "            G.add_edge(node.value, node.left.value)\n",
        "            add_edges(node.left, G, pos, level + 1, x - 1)\n",
        "        if node.right:\n",
        "            G.add_edge(node.value, node.right.value)\n",
        "            add_edges(node.right, G, pos, level + 1, x + 1)\n",
        "\n",
        "        return G, pos\n",
        "\n",
        "    G, pos = add_edges(root)\n",
        "    nx.draw(G, pos, with_labels=True, arrows=False, node_size=500)\n",
        "    plt.show()\n",
        "\n",
        "# Build the example tree\n",
        "root = TreeNode(10)\n",
        "n5 = addNode(root, 5, True)\n",
        "n30 = addNode(root, 30, False)\n",
        "n22 = addNode(n30, 22, True)\n",
        "n35 = addNode(n30, 35, False)\n",
        "\n",
        "# Draw the tree\n",
        "drawTree(root)\n",
        "successor = inorderSuccessor(n22)\n",
        "if successor:\n",
        "    print(\"Inorder successor of node with value\", n22.value, \"is:\", successor.value)\n",
        "else:\n",
        "    print(\"The node with value\", n22.value, \"has no inorder successor.\")\n",
        "successor = inorderSuccessor(n5)\n",
        "if successor:\n",
        "    print(\"Inorder successor of node with value\", n5.value, \"is:\", successor.value)\n",
        "else:\n",
        "    print(\"The node with value\", n5.value, \"has no inorder successor.\")"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "This function first checks if the node has a right subtree. If it does, it finds the minimum in the right subtree. If not, it moves up the tree until it finds a node that is a left child of its parent. This node's parent is the inorder successor. If such a node is not found, it means the given node is the rightmost node in the tree, and its inorder successor does not exist (in which case the function returns `None`)."
      ],
      "metadata": {
        "id": "yT7hYJXrr5wI"
      }
    }
  ]
}