Reference :-

http://www.geeksforgeeks.org/amazon-interview-experience-set-134-campus-sde

"Attempt 2 F2F – Round 3: Q3"

http://www.geeksforgeeks.org/amazon-interview-experience-set-134-campus-sde

"Attempt 2 F2F – Round 3: Q3"

**Problem statement :-**
An array is given whose every ith index is the child node of a[i] as shown in the example below. The root node is represented by -1.

**Find the height of the tree.I did it in linear time.**

```
```

`Input: parent[] = {1 2 -1 2}`

```
index 0 1 2 3
for index 2 value is -1. So it is root 2
for index and index 3 value is 2. So they are child of 2
2
/ \
1 3
for index 0 value is 1. So it is child of 1
2
/ \
1 3
/
0
```

```
```

`Height of this tree is 3`

```
```

**My approach :- **

Height of the tree = maximum number in the array + 1 = 2+1 =3

```
```

`Another example`

Input: parent[] = 1 3 -1 2 1 Index 0 1 2 3 4 Tree is 2 / 3 / 1 / \ 0 4 \ 5

```
```

`Height of this tree is 5`

My approach :-Height of the tree = maximum number in the array + 1 = 4+1 =5

## No comments:

## Post a Comment