Code_Craft_bottom_view.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNflTdo1JVnQHo+G6sSPekx",
      "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_bottom_view.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",
        "The horizontal distance of a binary tree node describes how far left or right the node will be when the tree is printed out.\n",
        "\n",
        "More rigorously, we can define it as follows:\n",
        "\n",
        "The horizontal distance of the root is 0.\n",
        "The horizontal distance of a left child is hd(parent) - 1.\n",
        "The horizontal distance of a right child is hd(parent) + 1.\n",
        "For example, for the following tree, hd(1) = -2, and hd(6) = 0.\n",
        "````\n",
        "             5\n",
        "          /     \\\n",
        "        3         7\n",
        "      /  \\      /   \\\n",
        "    1     4    6     9\n",
        "   /                /\n",
        "  0                8\n",
        "  ````\n",
        "The bottom view of a tree, then, consists of the lowest node at each horizontal distance. If there are two nodes at the same depth and horizontal distance, either is acceptable.\n",
        "\n",
        "For this tree, for example, the bottom view could be [0, 1, 3, 6, 8, 9].\n",
        "\n",
        "Given the root to a binary tree, return its bottom view."
      ],
      "metadata": {
        "id": "tH7CkhIN6Ovd"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Solution:\n",
        "To solve the problem of finding the bottom view of a binary tree, we will use a level-order traversal (BFS) approach. During the traversal, we will keep track of the horizontal distance for each node using a queue. This will allow us to map each horizontal distance to the node that appears last at that horizontal distance as we process the tree from top to bottom.\n",
        "\n",
        "Here's the plan:\n",
        "1. Use a queue to perform a level-order traversal. Each element in the queue will be a tuple containing the node and its corresponding horizontal distance.\n",
        "2. Use a dictionary to store the last node encountered at each horizontal distance.\n",
        "3. After completing the traversal, extract the bottom view nodes from the dictionary, sort them by their horizontal distances, and return the list of node values."
      ],
      "metadata": {
        "id": "itQ9Rbxe6Twn"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Implementation:\n",
        "Let's implement this in Python:"
      ],
      "metadata": {
        "id": "Cb3P4iVt6W-J"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "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 bottom_view(root):\n",
        "    if not root:\n",
        "        return []\n",
        "\n",
        "    # Dictionary to hold the last node at each horizontal distance\n",
        "    hd_node_map = {}\n",
        "\n",
        "    # Queue for level order traversal, storing tuples of (node, horizontal distance)\n",
        "    queue = [(root, 0)]\n",
        "\n",
        "    while queue:\n",
        "        current_node, hd = queue.pop(0)\n",
        "\n",
        "        # Store the current node as the last seen at this horizontal distance\n",
        "        hd_node_map[hd] = current_node.val\n",
        "\n",
        "        # Add left child to queue with horizontal distance -1\n",
        "        if current_node.left:\n",
        "            queue.append((current_node.left, hd - 1))\n",
        "\n",
        "        # Add right child to queue with horizontal distance +1\n",
        "        if current_node.right:\n",
        "            queue.append((current_node.right, hd + 1))"
      ],
      "metadata": {
        "id": "lve1Yewi6N4N"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "##Testing:"
      ],
      "metadata": {
        "id": "rmascGp76a_Q"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "kVX9PbNY6M7_",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "b6d68559-04d7-43ec-c510-31169cda2e44"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[0, 1, 3, 6, 8, 9]\n"
          ]
        }
      ],
      "source": [
        "root = TreeNode(5, TreeNode(3, TreeNode(1, TreeNode(0)), TreeNode(4)), TreeNode(7, TreeNode(6), TreeNode(9, TreeNode(8))))\n",
        "print(bottom_view(root))  # Output should be: [0, 1, 3, 6, 8, 9]"
      ]
    }
  ]
}