1 00:00:00,240 --> 00:00:01,470 Welcome back. 2 00:00:01,470 --> 00:00:03,180 Let's do this question. 3 00:00:03,180 --> 00:00:10,500 Given the root of a binary tree, return the inorder traversal of its nodes values. 4 00:00:10,560 --> 00:00:18,900 Write the iterative solution okay, so we are asked to implement a function which will spit out the 5 00:00:18,900 --> 00:00:22,050 inorder traversal of the given binary tree. 6 00:00:22,050 --> 00:00:29,400 And again notice this array over here does not consist of nodes, but rather just consists of the values 7 00:00:29,400 --> 00:00:31,200 of the respective nodes. 8 00:00:31,560 --> 00:00:33,780 So we are given an example over here. 9 00:00:33,780 --> 00:00:38,430 If this is the binary tree which is given to us, this is the expected output. 10 00:00:38,430 --> 00:00:45,360 And notice that this is the postorder traversal of this binary tree, where first we go left, then 11 00:00:45,360 --> 00:00:48,540 we go right, and then we visit the root node. 12 00:00:48,540 --> 00:00:51,660 So let's quickly take a look at this example over here. 13 00:00:51,660 --> 00:00:54,030 So we start at the root node. 14 00:00:54,030 --> 00:00:57,510 Then we go left because we first have to go left. 15 00:00:57,510 --> 00:01:01,530 So we come over here and this becomes the root node. 16 00:01:01,530 --> 00:01:06,960 But then before we process this node we have to go again left because there is a node over here. 17 00:01:06,960 --> 00:01:10,380 So we reach over here and then we try to go left. 18 00:01:10,380 --> 00:01:12,060 So there's nothing on the left. 19 00:01:12,060 --> 00:01:13,890 And then we try to go to the right. 20 00:01:13,890 --> 00:01:14,940 There's nothing on the right. 21 00:01:14,940 --> 00:01:19,620 And then we process the root node which at this point is this node over here. 22 00:01:19,620 --> 00:01:21,960 So that's how we get the value for over here. 23 00:01:21,960 --> 00:01:25,950 And then we come over here we're done with the left part. 24 00:01:25,950 --> 00:01:28,830 And notice after left we have to go to the right. 25 00:01:28,830 --> 00:01:32,190 So before we process this node over here we come to the right. 26 00:01:32,190 --> 00:01:34,290 And this becomes the root node. 27 00:01:34,290 --> 00:01:37,410 And then before we process this node we have to go left. 28 00:01:37,410 --> 00:01:38,940 So we come over here okay. 29 00:01:38,940 --> 00:01:40,380 And then we try to go left. 30 00:01:40,380 --> 00:01:41,430 There's nothing on the left. 31 00:01:41,430 --> 00:01:42,900 And we try to go to the right. 32 00:01:42,900 --> 00:01:43,950 There's nothing on the right. 33 00:01:43,950 --> 00:01:48,630 And we process the root node at this instance which is this node over here. 34 00:01:48,630 --> 00:01:50,580 So that's how you get seven over here. 35 00:01:50,580 --> 00:01:53,400 And then we come over here we try to go right. 36 00:01:53,400 --> 00:01:54,450 There's nothing on the right. 37 00:01:54,450 --> 00:01:57,060 So then we come over here which is the root node. 38 00:01:57,060 --> 00:01:58,560 So you get five over here okay. 39 00:01:58,560 --> 00:02:05,340 So notice at this point for this subtree over here we are done with the left part and we are done with 40 00:02:05,340 --> 00:02:06,120 the right part. 41 00:02:06,120 --> 00:02:12,120 Therefore now we visit the root node which is two for this subtree over here. 42 00:02:12,120 --> 00:02:14,040 And that's how we get two over here. 43 00:02:14,040 --> 00:02:16,050 And then we come over here okay. 44 00:02:16,050 --> 00:02:18,510 So this is the root node at this point. 45 00:02:18,510 --> 00:02:21,960 And we are done visiting the left part of this node. 46 00:02:21,960 --> 00:02:26,070 Now before we process this node over here we have to go to the right. 47 00:02:26,070 --> 00:02:32,220 So we come over here and before we process this node which is the root at this point we try to go to 48 00:02:32,220 --> 00:02:33,990 the left but there's nothing on the left. 49 00:02:33,990 --> 00:02:35,580 And then we try to go to the right. 50 00:02:35,580 --> 00:02:40,590 So we come over here and before we process this node we again go left. 51 00:02:40,590 --> 00:02:41,790 So we come over here. 52 00:02:41,790 --> 00:02:44,790 Now we again try to go left but there's nothing on the left. 53 00:02:44,790 --> 00:02:46,170 We try to go to the right. 54 00:02:46,170 --> 00:02:47,190 There's nothing on the right. 55 00:02:47,190 --> 00:02:51,030 And then we process this node which is the root at this point. 56 00:02:51,030 --> 00:02:52,770 So that's how you get eight over here. 57 00:02:52,770 --> 00:02:54,450 And then we come back over here. 58 00:02:54,450 --> 00:02:55,950 So we are done with the left part. 59 00:02:55,950 --> 00:02:58,620 We try to go to the right but there's nothing over here. 60 00:02:58,620 --> 00:03:01,980 And therefore we go ahead and process the root node which is six. 61 00:03:01,980 --> 00:03:03,240 So we get six over here. 62 00:03:03,240 --> 00:03:04,680 And then we're done with this. 63 00:03:04,680 --> 00:03:06,210 So we come over here. 64 00:03:06,210 --> 00:03:10,110 So we did try to go to the left but there was nothing on the left. 65 00:03:10,110 --> 00:03:12,870 And then we did process the right part as well. 66 00:03:12,870 --> 00:03:19,380 So therefore now we go ahead and process this node over here which is the root node for this subtree. 67 00:03:19,380 --> 00:03:20,940 So you get three over here. 68 00:03:20,940 --> 00:03:23,010 And at this point we come over here. 69 00:03:23,010 --> 00:03:29,430 Notice that we're done processing the left part of this node as well as the right part of this node. 70 00:03:29,430 --> 00:03:33,270 And therefore we go ahead and process the root node which is one. 71 00:03:33,270 --> 00:03:35,160 And therefore we get one over here. 72 00:03:35,160 --> 00:03:40,350 So that's why this is the postorder traversal of this binary tree over here. 73 00:03:40,680 --> 00:03:46,410 In the next video, let's try to think how we can solve this question in an iterative manner.