Breadth First Search (Linked List).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "3\n",
      "5\n",
      "4\n",
      "7\n",
      "2\n",
      "1\n",
      "3 2 5 1 4 7 "
     ]
    }
   ],
   "source": [
    "import sys\n",
    "\n",
    "class Node:\n",
    "    def __init__(self,data):\n",
    "        self.right=self.left=None\n",
    "        self.data = data\n",
    "class Solution:\n",
    "    def insert(self,root,data):\n",
    "        if root==None:\n",
    "            return Node(data)\n",
    "        else:\n",
    "            if data<=root.data:\n",
    "                cur=self.insert(root.left,data)\n",
    "                root.left=cur\n",
    "            else:\n",
    "                cur=self.insert(root.right,data)\n",
    "                root.right=cur\n",
    "        return root\n",
    "\n",
    "    def levelOrder(self,root): \n",
    "        h = Solution().height(root) \n",
    "        for i in range(1, h+1): \n",
    "            Solution().givenLevel(root, i) \n",
    "  \n",
    "  \n",
    "    def givenLevel(self,root,level=0): \n",
    "        if root is None: \n",
    "            return\n",
    "        if level == 1: \n",
    "            print(root.data,end=\" \") \n",
    "        elif level > 1 : \n",
    "            Solution().givenLevel(root.left,level-1) \n",
    "            Solution().givenLevel(root.right,level-1) \n",
    "  \n",
    "    def height(self,node): \n",
    "        if node is None: \n",
    "            return 0 \n",
    "        else :  \n",
    "            lheight = Solution().height(node.left) \n",
    "            rheight = Solution().height(node.right) \n",
    "  \n",
    "        if lheight > rheight : \n",
    "            return lheight+1\n",
    "        else: \n",
    "            return rheight+1 \n",
    " \n",
    "\n",
    "T=int(input())\n",
    "myTree=Solution()\n",
    "root=None\n",
    "for i in range(T):\n",
    "    data=int(input())\n",
    "    root=myTree.insert(root,data)\n",
    "myTree.levelOrder(root)"
   ]
  }
 ],
 "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.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}