Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

AVAILABLE LESSONS:

Lesson 1

Iterations

Lesson 2

Arrays

Lesson 3

Time Complexity

Lesson 4

Counting Elements

Lesson 5

Prefix Sums

Lesson 6

Sorting

Lesson 7

Stacks and Queues

Lesson 8

Leader

Lesson 9

Maximum slice problem

Lesson 10

Prime and composite numbers

Lesson 11

Sieve of Eratosthenes

Lesson 12

Euclidean algorithm

Lesson 13

Fibonacci numbers

Lesson 14

Binary search algorithm

Lesson 15

Caterpillar method

Lesson 16

Greedy algorithms

Lesson 17

Dynamic programming

Lesson 90

Tasks from Indeed Prime 2015 challenge

Lesson 91

Tasks from Indeed Prime 2016 challenge

Lesson 92

Tasks from Indeed Prime 2016 College Coders challenge

Lesson 99

Future training

painless

Compute the height of a binary tree.

Programming language:
Spoken language:

In this problem we consider binary trees, represented by pointer data structures.

A *binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

For example, the figure below shows a binary tree consisting of six nodes. Its root contains the value 5, and the roots of its left and right subtrees have the values 3 and 10, respectively. The right subtree of the node containing the value 10, as well as the left and right subtrees of the nodes containing the values 20, 21 and 1, are empty trees.

A *path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

The *height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

int solution(struct tree * T);

that, given a non-empty binary tree T consisting of N nodes, returns its height. For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.

A binary tree can be given using a pointer data structure. Assume that the following declarations are given:

struct tree { int x; struct tree * l; struct tree * r; };

An empty tree is represented by an empty pointer (denoted by `NULL`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by `None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..500].

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

In this problem we consider binary trees, represented by pointer data structures.

A *binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

For example, the figure below shows a binary tree consisting of six nodes. Its root contains the value 5, and the roots of its left and right subtrees have the values 3 and 10, respectively. The right subtree of the node containing the value 10, as well as the left and right subtrees of the nodes containing the values 20, 21 and 1, are empty trees.

A *path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

The *height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

int solution(tree * T);

that, given a non-empty binary tree T consisting of N nodes, returns its height. For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.

A binary tree can be given using a pointer data structure. Assume that the following declarations are given:

struct tree { int x; tree * l; tree * r; };

An empty tree is represented by an empty pointer (denoted by `NULL`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by `None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..500].

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

In this problem we consider binary trees, represented by pointer data structures.

A *binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

For example, the figure below shows a binary tree consisting of six nodes. Its root contains the value 5, and the roots of its left and right subtrees have the values 3 and 10, respectively. The right subtree of the node containing the value 10, as well as the left and right subtrees of the nodes containing the values 20, 21 and 1, are empty trees.

A *path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

The *height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

class Solution { public int solution(Tree T); }

that, given a non-empty binary tree T consisting of N nodes, returns its height. For example, given tree T shown in the figure above, the function should return 2, as explained above. Note that the values contained in the nodes are not relevant in this task.

A binary tree can be given using a pointer data structure. Assume that the following declarations are given:

class Tree { public int x; public Tree l; public Tree r; };

An empty tree is represented by an empty pointer (denoted by `null`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

For the purpose of entering your own test cases, you can denote a tree recursively in the following way. An empty binary tree is denoted by `None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];
- the height of tree T (number of edges on the longest path from root to leaf) is within the range [0..500].

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Copyright 2009–2018 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

func Solution(T *Tree) int

type Tree struct { X int L *Tree R *Tree }

An empty tree is represented by an empty pointer (denoted by `nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

class Solution { public int solution(Tree T); }

class Tree { public int x; public Tree l; public Tree r; }

An empty tree is represented by an empty pointer (denoted by `null`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

function solution(T);

// Tree obj is an Object with attributes // obj.x - type: int // obj.l - type: Tree // obj.r - type: Tree

An empty tree is represented by an empty pointer (denoted by `null`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

function solution(T)

-- Tree obj is an object with attributes -- obj.x - type: int -- obj.l - type: Tree -- obj.r - type: Tree

An empty tree is represented by an empty pointer (denoted by `nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

int solution(Tree * T);

@interface Tree : NSObject { @public int x; Tree * l; Tree * r; } @end @implementation Tree @end

An empty tree is represented by an empty pointer (denoted by `nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

function solution(T: Tree): longint;

Tree = ^TreeNode; TreeNode = record x : longint; l : Tree; r : Tree; end;

`nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

function solution($T);

class Tree { var $x = 0; var $l = NULL; var $r = NULL; }

An empty tree is represented by an empty pointer (denoted by `NULL`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

sub solution { my ($T)=@_; ... }

# Tree is a dictionary with keys # 'x' - type: int # 'l' - type: Tree # 'r' - type: Tree

An empty tree is represented by an empty pointer (denoted by `undef`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

def solution(T)

class Tree(object): x = 0 l = None r = None

An empty tree is represented by an empty pointer (denoted by `None`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

def solution(t)

class Tree attr_accessor :x, :l, :r end

`nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

object Solution { def solution(t: Tree): Int }

class Tree(var x: Int, var l: Tree, var r: Tree)

`null`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

public func solution(T : Tree?) -> Int

public class Tree { public var x : Int = 0 public var l : Tree? public var r : Tree? public init() {} }

`nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

public func solution(_ T : Tree?) -> Int

public class Tree { public var x : Int = 0 public var l : Tree? public var r : Tree? public init() {} }

`nil`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

In this problem we consider binary trees, represented by pointer data structures.

*binary tree* is either an empty tree or a node (called the *root*) consisting of a single integer value and two further binary trees, called the *left subtree* and the *right subtree*.

*path* in a binary tree is a non-empty sequence of nodes that one can traverse by following the pointers. The *length* of a path is the number of pointers it traverses. More formally, a path of length K is a sequence of nodes P[0], P[1], ..., P[K], such that node P[I + 1] is the root of the left or right subtree of P[I], for 0 ≤ I < K. For example, the sequence of nodes with values 5, 3, 21 is a path of length 2 in the tree from the above figure. The sequence of nodes with values 10, 1 is a path of length 1. The sequence of nodes with values 21, 3, 20 is not a valid path.

*height* of a binary tree is defined as the length of the longest possible path in the tree. In particular, a tree consisting of only one node has height 0 and, conventionally, an empty tree has height −1. For example, the tree shown in the above figure is of height 2.

Write a function:

Private Function solution(T As Tree) As Integer

Class Tree Public x As Integer Public l As Tree Public r As Tree End Class

An empty tree is represented by an empty pointer (denoted by `Nothing`). A non-empty tree is represented by a pointer to an object representing its root. The attribute `x` holds the integer contained in the root, whereas attributes `l` and `r` hold the left and right subtrees of the binary tree, respectively.

`None`. A non-empty tree is denoted as (X, L, R), where X is the value contained in the root and L and R denote the left and right subtrees, respectively. The tree from the above figure can be denoted as:

Assume that:

- N is an integer within the range [1..1,000];

Complexity:

- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N).

Information about upcoming challenges, solutions and lessons directly in your inbox.

© 2009–2018 Codility Ltd., registered in England and Wales (No. 7048726). VAT ID GB981191408. Registered office: 107 Cheapside, London EC2V 6DN