Colab_Codes/chapter_tree_data_structure_and_traversal.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "chapter_tree_data_structure_and_traversal.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "3A2mprldYvXe",
        "colab_type": "text"
      },
      "source": [
        "## Tree Representation\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "SYVbYid7SPos",
        "colab_type": "text"
      },
      "source": [
        "### N-aray Tree"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "9R_XYWC2Yz-G",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Define Tree Node\n",
        "class NaryNode:\n",
        "  def __init__(self, val, n):\n",
        "    self.children = [None] * n\n",
        "    self.val = val  "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cQfD7fA7WWPT",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "root = NaryNode(1, 2)\n",
        "left = NaryNode(2, 2)\n",
        "right = NaryNode(3, 2)\n",
        "# connect root to its left and right, the order does not matter\n",
        "root.children[0] = left\n",
        "root.children[1] = right\n",
        "left = NaryNode(4, 0)\n",
        "right = NaryNode(5, 5)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "wLPjQrfnZbQY",
        "colab_type": "text"
      },
      "source": [
        "### Binary Tree"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ZKknhNURZdA0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Binary Tree Node\n",
        "class BinaryNode:\n",
        "  def __init__(self, val):\n",
        "    self.left = None\n",
        "    self.right = None\n",
        "    self.val = val"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yPukXXkXZ_zn",
        "colab_type": "text"
      },
      "source": [
        "#### Tree Construction\n",
        "```\n",
        "      1\n",
        "    /   \\  \n",
        "   2      3\n",
        " /   \\      \\\n",
        "4     5      6 \n",
        "```"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "CyXwZ9sf8dyG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Naive Tree Construction\n",
        "root = BinaryNode(1)\n",
        "left = BinaryNode(2)\n",
        "right = BinaryNode(3)\n",
        "root.left = left\n",
        "root.right = right\n",
        "left.left = BinaryNode(4)\n",
        "left.right = BinaryNode(5)\n",
        "right.right = BinaryNode(6)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gOHqKKfY_Ug0",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Recursive Tree Construction\n",
        "def constructTree(a, idx):\n",
        "  '''\n",
        "  a: input array of nodes\n",
        "  idx: index to indicat the location of the current node\n",
        "  '''\n",
        "  if idx >= len(a):\n",
        "    return None\n",
        "  if a[idx]:\n",
        "    node = BinaryNode(a[idx])\n",
        "    node.left = constructTree(a, 2*idx + 1)\n",
        "    node.right = constructTree(a, 2*idx + 2)\n",
        "    return node\n",
        "  return None"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "STvuN-5p_5Di",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "nums = [1, 2, 3, 4, 5, None, 6]\n",
        "root = constructTree(nums, 0)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NsyaTExQIAos",
        "colab_type": "code",
        "outputId": "1681353d-30ad-4269-d273-cf939958e015",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "nums = [1] * 1_000_000\n",
        "print(nums.__sizeof__()/1024/1024)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "7.629432678222656\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "D4Bj_uMsHpAZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Constrcut a  large tree\n",
        "nums = [1] * 1_000_000\n",
        "#root = constructTree(nums, 0)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ymohgmrC9-ih",
        "colab_type": "text"
      },
      "source": [
        "## Tree Traversal"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "W4XlEDMn7ZE5",
        "colab_type": "text"
      },
      "source": [
        "### Depth-first Tree Traversal"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "U_ZjljRzugyQ",
        "colab_type": "text"
      },
      "source": [
        "#### Recursive Tree Traversal"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zERenCBy99sV",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Preorder Traversal\n",
        "def recursive(node):\n",
        "  if not node:\n",
        "    return\n",
        "  print(node.val, end=' ')\n",
        "  recursive(node.left)\n",
        "  recursive(node.right)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "M86_7JR7-cfu",
        "colab_type": "code",
        "outputId": "46132bdc-06ad-406b-8db4-ff08febe0a89",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "recursive(root)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 2 4 5 3 6 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "o1U3R9A8GvPr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Inorder Traversal\n",
        "def inorder_traversal(node):\n",
        "  if not node:\n",
        "    return\n",
        "  inorder_traversal(node.left)\n",
        "  print(node.val, end=' ')\n",
        "  inorder_traversal(node.right)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sy6hIovuG0dq",
        "colab_type": "code",
        "outputId": "ab4403e1-b5ac-4747-a388-30a79f2f2bc6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "inorder_traversal(root)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "4 2 5 1 3 6 "
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Si1c44bDKLkG",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Preorder traversal with returns\n",
        "def PreOrder(root):\n",
        "    if root is None:\n",
        "        return []\n",
        "    ans = []\n",
        "    # Divide and brings back the subresult\n",
        "    left = PreOrder(root.left)\n",
        "    right = PreOrder(root.right)\n",
        "    # Combine\n",
        "    ans = [root.val] + left + right\n",
        "    return ans"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tCVpSw9ALNEM",
        "colab_type": "code",
        "outputId": "30f7cb20-2abd-4a00-f978-e4609d2d6300",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "print(PreOrder(root))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "[1, 2, 4, 5, 3, 6]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "yxCOd-iZuc-s",
        "colab_type": "text"
      },
      "source": [
        "#### Iterative Tree Traversal"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "N43NhcugSfYN",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def PreOrderIterative(root):\n",
        "    if root is None:\n",
        "        return []\n",
        "    res = []\n",
        "    stack = [root]\n",
        "    while stack:\n",
        "        tmp = stack.pop()\n",
        "        res.append(tmp.val)\n",
        "        if tmp.right:\n",
        "            stack.append(tmp.right)\n",
        "        if tmp.left:\n",
        "            stack.append(tmp.left)\n",
        "    return res"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "5ay0zisQShpr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "preorders = PreOrderIterative(root)\n",
        "preorders"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iz2S46vA7ked",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def PostOrderIterative(root):\n",
        "    if root is None:\n",
        "        return []\n",
        "    res = []\n",
        "    stack = [root]\n",
        "    while stack:\n",
        "        tmp = stack.pop()\n",
        "        res.append(tmp.val)\n",
        "        if tmp.left:\n",
        "            stack.append(tmp.left)\n",
        "        if tmp.right:\n",
        "            stack.append(tmp.right)\n",
        "    return res[::-1]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "_SH4Cr6c7sP5",
        "colab_type": "code",
        "outputId": "7d956975-f3e2-46e3-d9d2-fe10c41bc8c6",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "postorders = PostOrderIterative(root)\n",
        "postorders"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[4, 5, 2, 6, 3, 1]"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 22
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "cxWckHgZupxE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Inorder and Preorder\n",
        "def iterative_traversal(root):\n",
        "  stack = []\n",
        "  cur = root\n",
        "  preorders = []\n",
        "  inorders = []\n",
        "  while stack or cur:\n",
        "    while cur:\n",
        "      preorders.append(cur.val)\n",
        "      stack.append(cur)\n",
        "      cur = cur.left\n",
        "    node = stack.pop()\n",
        "    inorders.append(node.val)\n",
        "    cur = node.right\n",
        "  return preorders, inorders"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "TFuu6oUmwwDq",
        "colab_type": "code",
        "outputId": "c54bfafe-5789-4538-a6bf-5a4f843ab75d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "preorders, inorders = iterative_traversal(root)\n",
        "preorders, inorders"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "([1, 2, 4, 5, 3, 6], [4, 2, 5, 1, 3, 6])"
            ]
          },
          "metadata": {
            "tags": []
          },
          "execution_count": 20
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GyJug1-77Re6",
        "colab_type": "text"
      },
      "source": [
        "### Breath-first Tree Traversal"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8IxSoqTthZb9",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Level Order Traversal: To show the nodes at each level, we use LevelOrder function to print out the tree:\n",
        "def LevelOrder(root):\n",
        "  if not root:\n",
        "    return\n",
        "  nodes_same_level = [root]\n",
        "  while nodes_same_level:\n",
        "    temp = []\n",
        "    for n in nodes_same_level:\n",
        "      print(n.val, end=' ')\n",
        "      if n.left:\n",
        "        temp.append(n.left)\n",
        "      if n.right:\n",
        "        temp.append(n.right)\n",
        "    nodes_same_level = temp"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "uPxVdjRrA0UB",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Use a queue\n",
        "def bfs(root):\n",
        "  if not root:\n",
        "    return\n",
        "  q = [root]\n",
        "  while q:\n",
        "    node = q.pop(0) # get node at the front of the queue\n",
        "    print(node.val, end=' ')\n",
        "    if node.left:\n",
        "      q.append(node.left)\n",
        "    if node.right:\n",
        "      q.append(node.right)\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Pl2HGcHkA4rT",
        "colab_type": "code",
        "outputId": "9df917c4-592e-4233-b48f-502ceef94f27",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 35
        }
      },
      "source": [
        "LevelOrder(root)"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 2 3 4 5 6 "
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}