The paper describes a method of formalized complexity analysis for algorithms that manipulate labeled binary trees. The analysis is based on the properties of the data structures and of the functions computed by the algorithms. A binary tree is defined as an oriented ordered tree each of whose nodes has outdegree of either 2 or 0. Each node v is uniquely identified by the path leading from the root to it, represented by a string \(road(v)\in \{L,R\}^*\) of symbols L (Left) or R (Right); each internal node is labeled by a nonterminal symbol from an alphabet \(V_ N\); each leaf is labeled by a terminal symbol from an alphabet \(V_ T\). The label of the node v is denoted by info(v) and the string of labels of the nodes on the path from the root to v, excluding the label of v itself, by rinf(v). The class of S-functions is then defined as the class of functions \(f(v)=f(road(v),r\inf (v),\inf o(v))\) whose value at a node v depends only on the type of subordination of the node in the tree. A further classification of S-functions is given, based on the properties of f being: - non decreasing: \(f(ac,qs,\tau)\leq f(abc,qrs,\tau)\) (Note: in the definitions, variables with an implicit universal quantification will be used, with the following meaning: \(a,b,c\in \{L,R\}^*\), paths; \(q,r,s\in V^*_ N\), strings of labels compatible, i.e., of the same length, with the paths a,b,c; \(e\in \{L,R\}\), unit length paths; \(\theta \in V_ N\), \(\tau \in V_ T\) and \(\mu \in V_ N\cup V_ T\), labels); - alternative: there are subalphabets \(V_{NR}\), \(V_{NL}\subseteq V_ N\) such that \(V_{NR}\cup V_{NL}=V_ N\) and \(f(aLb,q\theta r,\tau)\leq f(aRb,q\theta r,\tau)\) for \(\theta \in V_{NR}\) and \(f(aLb,q\theta r,\tau)\geq f(aRb,q\theta r,\tau)\) for \(\theta \in V_{NL};\) - terminally maximal: \(\exists \tau_{\max}\in V_ T\) \((f(b,s,\tau)\leq f(b,s,\tau_{\max});\) - nonterminally dominant: \(f(a,q,\theta)-f(b,r,\theta)\geq f(a,q,\tau_{\max})-f(b,r,\tau_{\max})\), for \(\tau_{\max}\) as above; - nonterminally maximal: \(\exists e_{\max}\in \{L,R\}\) \(\exists \theta_{\max}\in V_ N\) \((f(a_ 1ea_ 2,q_ 1\theta q_ 2,\mu)\leq f(a_ 1e_{\max}a_ 2,q_ 1\theta_{\max}q_ 2,\mu);\) - convex: \(f(a_ 1bc_ 1,q_ 1rs_ 1,\tau)-f(a_ 2bc_ 2,q_ 2rs_ 2,\tau)\geq f(a_ 1c_ 1,q_ 1s_ 1,\tau)-f(a_ 2c_ 2,q_ 2s_ 2,\tau);\) - additive if \(f(ae,q\theta,\mu)=f(a,q,\mu)+h(e,\theta);\) - multiplicative if \(f(ae,q\theta,\mu)=f(a,q,\mu)*h(e,\theta);\) - \(SP_ 1\) if it is nondecreasing, alternative, terminally maximal and convex; - \(Sp_ 2\) if it is nondecreasing alternative, terminally maximal and nonterminally dominant; - \(SM_ 1(SM_ 2)\) if the opposite function \(g(v)=-f(v)\) is \(SP_ 1(SP_ 2).\) More complex definitions, that cannot be given here, are those of triad- maximal, SPH (SMH), \(SPH_ 1\) \((SMH_ 1)\), \(SPH_ 2\) \((SMH_ 2)\), P(M)-additive and P(M)-multiplicative functions. Now, calculations over trees are modeled by tree stack transducers (TST), and the time complexity of algorithms is defined as the number of TST operations as a function of the input tree. In particular, algorithms are considered for which the total time T(D) of processing the tree D is the sum of the time for processing every single node, which is in turn given by an S-function: \[ T(D)=\sum_{v\in V}f(v,D). \] These algorithms are called S-algorithms, and can be classified on the basis of the properties of the associated S-function. For some classes of S-algorithms, some complexity properties, in particular the existence of ``extremal'' data structures, can be established only on the basis of the properties of the underlying S-function. The main results are the following: (1) For any \(SP_ i\)-algorithm \((SM_ i\)-algorithm), \(i=1,2\), and for any odd \(n\geq 3\), there exists a maximizing (minimizing) n-node stretched binary tree. (2) For any \(SPH_ i\)-algorithm \((SMH_ i\)-algorithm), \(i=1,2\), and for any odd \(n\geq 3\), maximizing (minimizing) tree is an n-node left-handed and/or right-handed binary tree with a certain distributions of labels on the nodes of the tree. (3) Let \(T_{1,\max}(n)\) and \(T_{2,\max}(n)\) (resp., \(T_{3,\min}(n)\) and \(T_{4,\min}(n))\) denote upper (resp., lower) analytic estimates of P-additive and P-multiplicative (resp., M-additive and M-multiplicative) algorithms. Then: \[ T_{1,\max}(n)=A_ 1n^ 2+B_ 1n+C_ 1;\quad T_{2,\max}(n)=A_ 2B^ n_ 2+C_ 2; \] \[ T_{3,\min}(n)=A_ 3n^ 2+B_ 3n+C_ 3;\quad T_{4,\min}(n)=A_ 4B^ n_ 4+C_ 4, \] where n is the number of tree nodes, and \(A_ i\), \(B_ i\), \(C_ i\) are constants.