Daily Coading Problem 08.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "80f23cfb",
   "metadata": {},
   "source": [
    "# Daily Coading Problem 08"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b02a78d1",
   "metadata": {},
   "source": [
    "This problem was asked by Google.\n",
    "\n",
    "A unival tree (which stands for \"universal value\") is a tree where all nodes under it have the same value.\n",
    "\n",
    "Given the root to a binary tree, count the number of unival subtrees.\n",
    "\n"
   ]
  },
  {
   "cell_type": "raw",
   "id": "d449752f",
   "metadata": {},
   "source": [
    "For example, the following tree has 5 unival subtrees:\n",
    "\n",
    "#   0\n",
    "#  / \\\n",
    "# 1   0\n",
    "#    / \\\n",
    "#   1   0\n",
    "#  / \\\n",
    "# 1   1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "dfb6bd94",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level: 0 parent:  None side: top Val: 0\n",
      "level: 1 parent:  0 side: left Val: 1\n",
      "level: 1 parent:  0 side: right Val: 0\n",
      "level: 2 parent:  0 side: left Val: 1\n",
      "level: 3 parent:  1 side: left Val: 1\n",
      "level: 3 parent:  1 side: right Val: 1\n",
      "level: 2 parent:  0 side: right Val: 0\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "def printTree(root, level = 0, side = \"top\", parent = \"None\"):\n",
    "    if root is not None:\n",
    "        print (\"level:\", str(level), \"parent: \", parent, \"side:\", side, \"Val:\", str(root.val))\n",
    "    \n",
    "    if root.left is not None:\n",
    "        printTree(root.left, level + 1, \"left\", str(root.val))\n",
    "    \n",
    "    if root.right is not None:\n",
    "        printTree(root.right, level + 1, \"right\", str(root.val))\n",
    "\n",
    "def numUnival_inner(root):\n",
    "    if root is None:\n",
    "        return 0, True\n",
    "    \n",
    "    countLeft, isLeftUnival = numUnival_inner(root.left)\n",
    "    countRight, isRightUnival = numUnival_inner(root.right)\n",
    "    total = countLeft + countRight\n",
    "    \n",
    "    if isLeftUnival and isRightUnival:\n",
    "        if root.left is not None and root.left.val != root.val:\n",
    "            return total, False\n",
    "        elif root.right is not None and root.right.val != root.val:\n",
    "            return total, False\n",
    "        else:\n",
    "            return total + 1, True\n",
    "    else:\n",
    "        return total, False\n",
    "    \n",
    "\n",
    "def numUnival(root):\n",
    "    count, _ = numUnival_inner(root)\n",
    "    return count\n",
    "\n",
    "\n",
    "root = Node(0, Node(1), Node(0, Node(1, Node(1), Node(1)), Node(0))) # => 5\n",
    "#root = Node(0, Node(0, Node(0), Node(0)), Node(0, Node(0), Node(0))) # => 7\n",
    "#root = Node(0, Node(1, Node(0), Node(0)), Node(1, Node(0), Node(0))) # => 4\n",
    "#root = Node(0, Node(0), Node(0, Node(0), Node(0, None, Node(1))))\n",
    "#root = Node(0)\n",
    "#root.left = Node(0)\n",
    "#root.right = Node(0)\n",
    "#root.right.left = Node(0)\n",
    "#root.right.right = Node(0)\n",
    "#root.right.right.left = None\n",
    "#root.right.right.right = Node(1)\n",
    "\n",
    "printTree(root)\n",
    "print (numUnival(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5e0707ca",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}