Skip to main content
Code Golf

Questions tagged [binary-tree]

Ask Question

A high-level data structure, made of nodes, each with a maximum of 2 children (left and right). Nodes with no children are called leaves, and two nodes with the same parent are known as siblings.

33 questions
Newest Active Bountied Unanswered
Filter by
Sorted by
Tagged with
8 votes
6 answers
1k views

Let N = [0,1,2,...n-1] be the initial segment of the natural numbers of length n, then all permutations of N can be sorted lexicographically, starting with the identity. The index into this sorted ...
Sophia Antipolis's user avatar
  • 1,742
8 votes
5 answers
851 views

Objective Given a positive reduced fraction, output its parent in the Stern-Brocot tree. The outputted fraction shall also be reduced. The Stern-Brocot tree The Stern-Brocot tree is an infinite-height ...
Dannyu NDos's user avatar
  • 7,381
11 votes
13 answers
1k views

For prime p, the factorization tree is a single vertex in just one way so that a(p) = 1. For composite n, the two subtrees at n are a split of n into two factors n = d * (n/d), without order, so that $...
Sophia Antipolis's user avatar
  • 1,742
11 votes
9 answers
1k views

Objective Given an unlabelled binary tree, decide whether it is contiguous in indices. Indices This challenge gives one-indexing on binary trees. The exact definition expresses all indices in binary ...
Dannyu NDos's user avatar
  • 7,381
11 votes
14 answers
852 views

For this challenge a "binary tree" is a rooted tree where each node has 0 children (leaf) or 2. The children of a node are unordered, meaning that while you might draw the tree with left ...
Wheat Wizard's user avatar
  • 103k
28 votes
12 answers
2k views

Consider a binary tree built the following way: The root node is \$1\$ For a given node \$n\$: If \$n\$ is odd, its only child is \$2n\$ If \$n\$ is even, one of its children is \$2n\$. If \$\frac {...
caird coinheringaahing's user avatar
  • 50.9k
12 votes
1 answer
312 views

Sandbox Inspired by a Codingame challenge I tried (and failed at) about a month ago. Given a binary tree of words, say: ...
Razetime's user avatar
  • 27.6k
16 votes
8 answers
363 views

Task Given a list of nodes representing a binary tree of positive integers serialized depth-first, return a list of nodes representing the same tree serialized breadth-first. To represent an absent ...
user's user avatar
  • 457
4 votes
3 answers
6k views

Maximillian is the chief commander of the Great Greek Army and he is leading his forces into a crucial war with Spain. If all the enemy soldiers stand in a straight line incrementally marked starting ...
Pluviophile's user avatar
  • 337
17 votes
2 answers
879 views

An unrooted binary tree is an unrooted tree (a graph that has single connected component and contains no cycles) where each vertex has exactly one or three neighbors. It is used in bioinformatics to ...
Bubbler's user avatar
  • 79.3k
20 votes
20 answers
3k views

Background Fibonacci trees \$T_n\$ are a sequence of rooted binary trees of height \$n-1\$. They are defined as follows: \$T_0\$ has no nodes. \$T_1\$ has a single node (the root). The root node of \$...
Bubbler's user avatar
  • 79.3k
8 votes
2 answers
425 views

Deserializing binary trees depth-first is pretty easy, but doing it breadth-first is (hopefully) harder. Your mission, should you choose to accept it, is to do the latter. The input will be a 1-D list ...
user's user avatar
  • 457
5 votes
8 answers
708 views

Any two separate nodes in a binary tree have a common ancestor, which is the root of a binary tree. The lowest common ancestor(LCA) is thus defined as the node that is furthest from the root and that ...
T. Salim's user avatar
  • 665
18 votes
11 answers
6k views

For each node in a balanced binary tree, the maximum difference in the heights of the left child subtree and the right child subtree are at most 1. The height of a binary tree is the distance from the ...
T. Salim's user avatar
  • 665
20 votes
20 answers
7k views

The height of a binary tree is the distance from the root node to the node child that is farthest from the root. Below is an example: ...
T. Salim's user avatar
  • 665
25 votes
16 answers
2k views

Background A binary tree is a rooted tree whose every node has at most two children. A labelled binary tree is a binary tree whose every node is labelled with a positive integer; moreover, all ...
Delfad0r's user avatar
  • 6,276
17 votes
7 answers
1k views

Balanced binary search trees are essential to guarantee O(log n) lookups (or similar operations). In a dynamic environment where a lot of keys are randomly inserted and/or deleted, trees might ...
ბიმო's user avatar
  • 17k
15 votes
12 answers
2k views

Given a binary number, your task is to create a 'branch' of that number, with a depth of 2. For example, given 0 as input, you should output exactly this: ...
Okx's user avatar
  • 16.5k
20 votes
9 answers
2k views

Binary trees A binary tree is a tree with nodes of three types: terminal nodes, which have no children unary nodes, which have one child each binary nodes, which have two children each We can ...
Guy Coder's user avatar
  • 321
24 votes
7 answers
1k views

Inspired by A014486. Challenge Given an integer input in base 10, construct a representation for the binary forest corresponding to the input. Representations include, but are not limited to, nested ...
JungHwan Min's user avatar
  • 14k
46 votes
4 answers
3k views

An aesthetically pleasing divisor tree is a tree of divisors of input n that, for any composite number m, has two children nodes ...
Sherlock9's user avatar
  • 12.4k
15 votes
5 answers
762 views

Task Given the pre-order and post-order traversals of a full binary tree, return its in-order traversal. The traversals will be represented as two lists, both containing n distinct positive integers,...
lynn's user avatar
  • 69.7k
10 votes
1 answer
322 views

Have you heard about trees? When performing DFS on a binary tree, you can traverse it in 3 possible orders. Root, left node, right node (Pre-order) Left node, Root, right node (In-order) Left node, ...
jkklapp's user avatar
  • 126
7 votes
1 answer
478 views

Brief Print an ASCII representation of a binary search tree. You should write your own minimum implementation logic of a BST (node, left, right, insert) (50,30,70,20,80,40,75,90) gives: ...
Denham Coote's user avatar
  • 1,437
7 votes
5 answers
5k views

Write the shortest possible program that turns a binary search tree into an ordered doubly-linked list, by modifying the pointers to the left and the right children of each node. Arguments: a pointer ...
user avatar
9 votes
6 answers
1k views

Write a program that takes a binary tree as input, and outputs the deepest node and its depth. If there is a tie, print all involved nodes as well as their depths. Each node is represented as: ...
Jwosty's user avatar
  • 3,594
8 votes
6 answers
2k views

In informatics, we often use trees in lots of different forms and representations. The three major methods of serialising binary trees are prefix, infix and postfix notation. For example, the ...
tomsmeding's user avatar
  • 2,054
15 votes
12 answers
3k views

Given a unique, sorted list of integers, create a balanced binary-search tree represented as an array without using recursion. For example: ...
Jake Wharton's user avatar
  • 319
16 votes
10 answers
3k views

The Stern-Brocot tree is a binary tree of fractions where each fraction is acquired by adding the numerators and denominators of the two fractions neighbouring it in the levels above. It is generated ...
Joe Z.'s user avatar
  • 35.5k
10 votes
8 answers
2k views

Given an integer n, enumerate all possible full binary trees with n internal nodes. (Full binary trees have exactly 2 children on every internal node). The tree structure should be output as a pre-...
Kyle Butt's user avatar
  • 203
10 votes
5 answers
983 views

Write a filter that converts text from standard input to a representation of its Huffman tree on standard output. In as few characters as possible. you're free to consider newlines or not output ...
J B's user avatar
  • 10.1k
20 votes
5 answers
8k views

Inspired by a recent question on SO... Write a function to print a binary tree in the following format: 3 / \ 1 5 \ / \ 2 4 6 The output should ...
Anon.'s user avatar
  • 1,879
14 votes
5 answers
12k views

So before you read some basic computer science concepts. A binary tree is a dynamically allocated structure (usually used for ordered storage). Because of its nature traversal of binary trees is ...
Loki Astari's user avatar
  • 966