dfs/on_tree/balanced_binary_tree

class Node:
	def __init__(self, val, left, right):
		self.val = val
		self.left = left
		self.right = right

def dfs(tree: Node):
	if tree is None:
		return 0
	left = dfs(tree.left)
	right = dfs(tree.right)
	if (left == -1 or right == -1):
		return -1
	if (abs(left - right) > 1):
		return -1
	return max(left, right) + 1

def is_balanced(tree: Node):
	return dfs(tree) != -1;

def build_tree(nodes, f):
    val = next(nodes)
    if val == "x":
        return None
    left = build_tree(nodes, f)
    right = build_tree(nodes, f)
    return Node(f(val), left, right)

if __name__ == "__main__":
    tree = build_tree(iter(input().split()), int)
    res = is_balanced(tree)
    print("true" if res else "false")

#include <algorithm>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

template<typename T>
struct Node {
	T val;
	Node<T>* left;
	Node<T>* right;

	explicit Node(T val, Node<T>* left = nullptr, Node<T>* right = nullptr) 
		: val{val}, left{left}, right{right} {}

	~Node() {
		delete left;
		delete right;
	}
};

int tree_height(Node<int>* tree) {
	if (tree == nullptr) return 0;
	int left_height = tree_height(tree->left);
	int right_height = tree_height(tree->right);
	if (left_height == -1 || right_height == -1) return -1;
	if (std::abs(left_height - right_height) > 1) return -1;
	return std::max(left_height, right_height) + 1;
}

bool is_balanced(Node<int>* tree) {
	// WRITE YOUR BRILLIANT CODE HERE
	return tree_height(tree) != -1;
}

// this function builds a tree from input
// learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
template<typename T, typename Iter, typename F>
Node<T>* build_tree(Iter& it, F f) {
	std::string val = *it;
	++it;
	if (val == "x") return nullptr;
	Node<T>* left = build_tree<T>(it, f);
	Node<T>* right = build_tree<T>(it, f);
	return new Node<T>{f(val), left, right};
}

template<typename T>
std::vector<T> get_words() {
	std::string line;
	std::getline(std::cin, line);
	std::istringstream ss{line};
	ss >> std::boolalpha;
	std::vector<T> v;
	std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
	return v;
}

int main() {
	std::vector<std::string> tree_vec = get_words<std::string>();
	auto tree_it = tree_vec.begin();
	Node<int>* tree = build_tree<int>(tree_it, [](auto s) { return std::stoi(s); });
	bool res = is_balanced(tree);
	std::cout << std::boolalpha << res << '\n';
}

"use strict";

class Node {
	constructor(val, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function dfs(tree) {
	if (tree === null) return 0;
	const left = dfs(tree.left);
	const right = dfs(tree.right);
	if (left === -1 || right === -1) return -1;
	if (Math.abs(left - right) > 1) return -1;
	return Math.max(left, right) + 1;
}

function isBalanced(tree) {
	return dfs(tree) !== -1;
}

function buildTree(nodes, f) {
	const val = nodes.next().value;
	if (val === "x") return null;
	const left = buildTree(nodes, f);
	const right = buildTree(nodes, f);
	return new Node(f(val), left, right);
};

function splitWords(s) {
	return s === "" ? [] : s.split(" ");  
};

function* main() {
	const tree = buildTree(splitWords(yield)[Symbol.iterator](), parseInt);
	const res = isBalanced(tree);
	console.log(res);
}

class EOFError extends Error {}
{
    const gen = main();
    const next = (line) => gen.next(line).done && process.exit();
    let buf = "";
    next();
    process.stdin.setEncoding("utf8");
    process.stdin.on("data", (data) => {
        const lines = (buf + data).split("\n");
        buf = lines.pop();
        lines.forEach(next);
    });
    process.stdin.on("end", () => {
        buf && next(buf);
        gen.throw(new EOFError());
    });
}