Tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self, val, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Size of a binary tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def size(node)\n",
    "    if not node: return 0\n",
    "    return size(node.left)+size(node.right)+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Height of a binary tree "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def height(root):\n",
    "    if root==None: return 0\n",
    "    return max(height(root.left), height(root.right))+1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Count Leaf Nodes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def countLeaves(root):\n",
    "    if root==None: return 0 \n",
    "    if not root.left and not root.right: return 1\n",
    "    return countLeaves(root.left)+countLeaves(root.right)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LCA in BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def LCA(root,n1,n2):  # n1 and n2 are int and should also return int\n",
    "    while(root):\n",
    "        if root.val==n1: return n1\n",
    "        if root.val==n2: return n2\n",
    "        if n1<root.val<n2 or n1>root.val>n2: return root.val\n",
    "        if n1>root.val and n2>root.val:\n",
    "            root = root.right\n",
    "        if n1<root.val and n2<root.val:\n",
    "            root = root.left\n",
    "    return root.val\n",
    "\n",
    "def LCA(root,n1,n2):\n",
    "    while(root):\n",
    "        if root.val>n1 and root.val>n2:\n",
    "            root = root.left\n",
    "        elif root.val<n1 and root.val<n2:\n",
    "            root = root.right\n",
    "        else:\n",
    "            break\n",
    "    return root\n",
    "\n",
    "def LCA(root,n1,n2):\n",
    "    if root.val>max(n1,n2): return LCA(root.left,n1,n2)\n",
    "    elif root.val<min(n1,n2): return LCA(root.right,n1,n2)\n",
    "    else: return root.val\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LCA in Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## If Trees are Identical"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isIdentical(root1, root2):\n",
    "    if root1==root2==None: return True\n",
    "    if root1==None or root2==None: return False\n",
    "    return root1.data==root2.data and isIdentical(root1.left, root2.left) and isIdentical(root1.right, root2.right) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Check if Tree is Balanced"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def checkIsBalanced(root):\n",
    "    if root==None: return 0, True\n",
    "    ldepth, lbalanced = checkIsBalanced(root.left)\n",
    "    rdepth, rbalanced = checkIsBalanced(root.right)\n",
    "    return max(ldepth, rdepth)+1, lbalanced and rbalanced and abs(ldepth-rdepth)<=1\n",
    "    \n",
    "def isBalanced(root):\n",
    "    return checkIsBalanced(root)[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## If is Valid BST"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isValidBST(root, left=float('-inf'), right=float('inf')) -> bool:\n",
    "    return not root or left<root.val<right and \\\n",
    "    self.isValidBST(root.left,left,root.val) and \\\n",
    "    self.isValidBST(root.right,root.val,right)  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}